Unique (Optimal) Solutions: Complexity Results for Identifying and Locating-Dominating Codes - Laboratoire Interdisciplinaire des Sciences du Numérique Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2019

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

Résumé

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.
Fichier principal
Vignette du fichier
OH-AL-TCS-IdLD.pdf (323.38 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01884809 , version 1 (30-11-2020)

Identifiants

Citer

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⟩
151 Consultations
318 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More