Skip to Main content Skip to Navigation
Journal articles

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

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 ≥ 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.
Document type :
Journal articles
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-01884809
Contributor : Antoine Lobstein Connect in order to contact the contributor
Submitted on : Monday, November 30, 2020 - 1:36:43 PM
Last modification on : Wednesday, November 3, 2021 - 8:19:36 AM
Long-term archiving on: : Monday, March 1, 2021 - 7:03:20 PM

File

OH-AL-TCS-IdLD.pdf
Files produced by the author(s)

Identifiers

Citation

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

Share

Metrics

Record views

182

Files downloads

127