HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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, January 26, 2022 - 2:38:50 PM
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

112

Files downloads

142