Unique (Optimal) Solutions: Complexity Results for Identifying and Locating-Dominating Codes

Olivier Hudry (1) , Antoine Lobstein (2)

1 LTCI - Laboratoire Traitement et Communication de l'Information
2 GALaC - LRI - Graphes, Algorithmes et Combinatoire (LRI)

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 ≥ 1 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.

Keywords: Complexity theory; Graph theory; Uniqueness of solution; Polynomial reduction; Locating–dominating codes; Identifying codes; Complexity Theory; Graph Theory; Uniqueness of Solution; Polynomial Reduction; Locating-Dominating Codes; Identifying Codes

Domains: Computer Science [cs]; Computational Complexity [cs.CC]

Olivier Hudry, Antoine Lobstein. Unique (Optimal) Solutions: Complexity Results for Identifying and Locating-Dominating Codes. Theoretical Computer Science, 2019, 767, pp.83-102. ⟨10.1016/j.tcs.2018.09.034⟩. ⟨hal-01884809⟩