NP-Completeness of Independent Locating-Dominating Sets in Planar Bipartite and Subcubic Graphs - Lemos, Dayllon V. X.; Cappelle, Márcia R.; Coelho, Erika M. M.; Foulds, Leslie R.; Longo, Humberto J. (Anais do Encontro de Teoria da Computação (ETC), 2026)
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.