Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.21067 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915638061039616 |
|---|---|
| author | Banik, Aritra Patra, Praneet Kumar Rescigno, Adele Anna Sahu, Abhishek |
| author_facet | Banik, Aritra Patra, Praneet Kumar Rescigno, Adele Anna Sahu, Abhishek |
| contents | The Identifying Code (IC) problem seeks a vertex subset whose intersection with every vertex's closed neighborhood is unique, enabling fault detection in multiprocessor systems and practical uses in identity verification, environmental monitoring, and dynamic localization. A closely related problem is the Locating-Dominating Set (LD), which requires each non-dominating vertex to be uniquely identified by its intersection with the set. Cappelle, Gomes, and Santos (2021) proved that LD is W-hard for minimum clique cover and lacks polynomial kernels for parameters such as vertex cover, but their methods did not apply to IC. This paper answers their question by showing that IC does not admit a polynomial kernel parameterized by solution size plus vertex cover unless NP is a subset of coNP/poly. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_21067 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Identifying Codes Kernelization Limitations Banik, Aritra Patra, Praneet Kumar Rescigno, Adele Anna Sahu, Abhishek Computational Complexity The Identifying Code (IC) problem seeks a vertex subset whose intersection with every vertex's closed neighborhood is unique, enabling fault detection in multiprocessor systems and practical uses in identity verification, environmental monitoring, and dynamic localization. A closely related problem is the Locating-Dominating Set (LD), which requires each non-dominating vertex to be uniquely identified by its intersection with the set. Cappelle, Gomes, and Santos (2021) proved that LD is W-hard for minimum clique cover and lacks polynomial kernels for parameters such as vertex cover, but their methods did not apply to IC. This paper answers their question by showing that IC does not admit a polynomial kernel parameterized by solution size plus vertex cover unless NP is a subset of coNP/poly. |
| title | Identifying Codes Kernelization Limitations |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2511.21067 |