Complexity of Unique (Optimal) Solutions in Graphs: Vertex Cover and Domination

Olivier Hudry (1) , Antoine Lobstein (2)

1 Télécom ParisTech
2 GALaC - LRI - Graphes, Algorithmes et Combinatoire (LRI)

We study the complexity of four decision problems dealing with the uniqueness of a solution in a graph: "Uniqueness of a Vertex Cover with bounded size"(U-VC) and "Uniqueness of an Optimal Vertex Cover"(U-OVC), and for any fixed integer r ≥ 1, "Uniqueness of an r-Dominating Code with bounded size" (U-DCr) and "Uniqueness of an Optimal r-Dominating Code" (U-ODCr). In particular, we give a polynomial reduction from "Unique Satisfiability of a Boolean formula" (U-SAT

Keywords: Graph Theory; Complexity Theory; NP-Hardness; Decision Problems; Polynomial Reduction; Uniqueness of (Optimal) Solution; Domination; Dominating Codes; Vertex Covers; Boolean Satisfiability Problems

Domains: Mathematics [math]; Computer Science [cs]

Olivier Hudry, Antoine Lobstein. Complexity of Unique (Optimal) Solutions in Graphs: Vertex Cover and Domination. Journal of Combinatorial Mathematics and Combinatorial Computing, 2019, 110, pp.217-240. ⟨hal-01613388⟩