Unique (optimal) solutions: Complexity results for identifying and locating–dominating codes

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-LDC _r ), “Uniqueness of an Optimal r-Locating–Dominating Code” (U-OLDC _r ), “Uniqueness of an r-Identifying Code with bounded size” (U-IdC _r ), “Uniqueness of an Optimal r-Identifying Code” (U-OIdC _r ), for any fixed integer r≥1. In particular, we describe a polynomial reduction from “Unique Satisfiability of a Boolean formula” (U-SAT) to U-OLDC _r , and from U-SAT to U-OIdC _r ; for U-LDC _r and U-IdC _r , 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-LDC _r and U-IdC _r belong to the class DP.