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

https://hal.archives-ouvertes.fr/hal-01613388
Contributor : Antoine Lobstein Connect in order to contact the contributor
Submitted on : Monday, November 30, 2020 - 1:03:50 PM
Last modification on : Friday, July 9, 2021 - 4:35:29 AM
Long-term archiving on: : Monday, March 1, 2021 - 6:59:38 PM

File

OH-AL-VCandDom.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01613388, version 1

Citation

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⟩

Share

Metrics

Record views

348

Files downloads

50