Complexity of Unique (Optimal) Solutions in Graphs: Vertex Cover and Domination
Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 110, pp. 217-240, 2019.
Olivier HUDRY (#) & Antoine LOBSTEIN (*)
(#) Département Informatique et Réseaux, LTCI,
Télécom ParisTech, Université Paris-Saclay,
46 rue Barrault, 75634 Paris Cedex 13 - France
olivier.hudry@telecom-paristech.fr
(*) Centre National de la Recherche Scientifique,
Laboratoire de Recherche en Informatique, UMR 8623,
Université Paris-Sud, Université Paris-Saclay,
Bâtiment 650 Ada Lovelace, 91405 Orsay Cedex - France
antoine.lobstein@lri.fr
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>0, ``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) to U-OVC, and from U-SAT to U-ODCr. We prove that U-VC and U-DCr have complexity equivalent to that of U-SAT (up to polynomials); consequently, these problems are all NP-hard, and U-VC and U-DCr belong to the class DP.