Skip to Main content Skip to Navigation
Journal articles

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

Abstract : 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
Document type :
Journal articles
Complete list of metadata
Contributor : Antoine Lobstein Connect in order to contact the contributor
Submitted on : Monday, November 30, 2020 - 1:03:50 PM
Last modification on : Saturday, June 25, 2022 - 10:50:50 PM
Long-term archiving on: : Monday, March 1, 2021 - 6:59:38 PM


Files produced by the author(s)


  • HAL Id : hal-01613388, version 1


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



Record views


Files downloads