Liar's Domination in Unit Disk Graphs

Abstrakt

In this article, we study a variant of the minimum dominating set problem known as the minimum liar's dominating set (MLDS) problem. We prove that the MLDS problem is NP-hard in unit disk graphs. We point out that the approximation guarantee of for the approximation algorithm for unit disk graphs proposed by Banerjee and Bhore (2019) [11] is not correct and we propose a simple time 7.31-factor approximation algorithm, where n and m are the number of vertices and edges, respectively, in the given unit disk graph. Finally, we prove that the MLDS problem admits a polynomial-time approximation scheme.