NP-Completeness of Independent Locating-Dominating Sets in Planar Bipartite and Subcubic Graphs

• Dayllon V. X. Lemos UFG
• Márcia R. Cappelle UFG
• Erika M. M. Coelho UFG
• Leslie R. Foulds UFG
• Humberto J. Longo UFG

DOI: https://doi.org/10.5753/etc.2026.23370

Resumo

The Independent Locating-Dominating Set (ILD) problem consists of determining whether a graph admits a vertex subset that is simultaneously independent, dominating, and able to uniquely identify all non-selected vertices. In this paper, we study the computational complexity of the ILD problem in restricted graph classes and prove that it remains NP-complete for planar bipartite graphs and planar triangle-free subcubic graphs, via polynomial-time reductions from variants of the 3-SAT problem.

Referências

Berman, P. R., Karpinski, M., and Scott, A. D. (2003). Approximation hardness and satisfiability of bounded occurrence instances of sat. Technical Report TR03-022, Computational Complexity Foundation (CCF), Electronic Colloquium on Computational Complexity. ISSN 1433-8092.

Chakraborty, D., Foucaud, F., Majumdar, D., and Tale, P. (2025). Structural parameterization of locating-dominating set and test cover. In Algorithms and Complexity: 14th International Conference, CIAC 2025, Rome, Italy, June 10–12, 2025, Proceedings, Part I, page 187–204, Berlin, Heidelberg. Springer-Verlag.

Foucaud, F. (2015). Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes. Journal of Discrete Algorithms, 31:48–68. 24th International Workshop on Combinatorial Algorithms (IWOCA 2013).

Lemos, D. V. X., Cappelle, M. R., Coelho, E. M. M., Foulds, L. R., and Longo, H. J. (2025a). Independent locating-dominating sets in P4-sparse graphs. In Anais do X Encontro de Teoria da Computação, pages 41–45, Porto Alegre, RS, Brasil. SBC.

Lemos, D. V. X., Cappelle, M. R., Coelho, E. M. M., Foulds, L. R., and Longo, H. J. (2025b). Independent Locating-Dominating Sets in Some Graphs Constructed from Cycles. Matemática Contemporânea.

Müller, T., Sereni, J.-S., and Muller, T. (2009). Identifying and locating-dominating codes in (random) geometric networks. Combinatorics, Probability and Computing, 18(6):925–952.

Rahbani, H., Rad, N. J., and Sadeghi, M.-R. (2019). A note on the complexity of locating-total domination in graphs. Theoretical Computer Science, 799:32–39.

Rall, D. and Slater, P. (1984). On location-domination numbers for certain classes of graphs. Congressus Numerantium, 45(1):97–106.

Slater, P. J. and Sewell, J. L. (2018). Independent locating-dominating sets and independent identifying codes in graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 104:261–272.