Complexity of Unique (Optimal) Solutions in Graphs: Vertex Cover and Domination - Graphes, Algorithmes et Combinatoire Access content directly
Journal Articles Journal of Combinatorial Mathematics and Combinatorial Computing Year : 2019

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

Olivier Hudry
Antoine Lobstein

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
Fichier principal
Vignette du fichier
OH-AL-VCandDom.pdf (231.25 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-01613388 , version 1 (30-11-2020)

Identifiers

  • HAL Id : hal-01613388 , version 1

Cite

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⟩
283 View
227 Download

Share

Gmail Mastodon Facebook X LinkedIn More