Unique (Optimal) Solutions: Complexity Results for Identifying and Locating-Dominating Codes
Theoretical Computer Science, Vol. 767, pp. 83-102, 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 investigate the complexity of four decision problems dealing with the uniqueness of a solution in a graph: ``Uniqueness of an r-Locating-Dominating Code with bounded size'' (U-LDCr), ``Uniqueness of an Optimal r-Locating-Dominating Code'' (U-OLDCr), ``Uniqueness of an r-Identifying Code with bounded size'' (U-IdCr), ``Uniqueness of an Optimal r-Identifying Code'' (U-OIdCr), for any fixed integer r>0.
In particular, we describe a polynomial reduction from ``Unique Satisfiability of a Boolean formula'' (U-SAT) to U-OLDCr, and from U-SAT to U-OIdCr; for U-LDCr and U-IdCr, we can do even better and prove that their complexity is the same as that of U-SAT, up to polynomials. Consequently, all these problems are NP-hard, and U-LDCr and U-IdCr belong to the class DP.