2019/02/27 by Sandip Banerjee, Banerjee, Sandip, Sujoy Bhore +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Search Problems #cs.CC #cs.CG #cs.DM
paper · pdf · doi:10.48550/arxiv.1902.11149
Appears in the Proceedings of the 30th International Workshop on Combinatorial Algorithms (IWOCA 2019)
openalex publication_date 2019/02/27 · arxiv created 2019/11/24 · arxiv updated 2019/11/26 · openalex created_date 2022/07/29 · openalex updated_date 2026/07/28
Given a graph G=(V,E), the dominating set problem asks for a minimum subset of vertices D⊆ V such that every vertex u∈ V∖ D is adjacent to at least one vertex v∈ D. That is, the set D satisfies the condition that |N[v]∩ D|≥ 1 for each v∈ V, where N[v] is the closed neighborhood of v. In this paper, we study two variants of the classical dominating set problem: \boldmathk-tuple dominating set (k-DS) problem and Liar's dominating set (LDS) problem, and obtain several algorithmic and hardness results. On the algorithmic side, we present a constant factor ((11)/(2))-approximation algorithm for the Liar's dominating set problem on unit disk graphs. Then, we obtain a PTAS for the \boldmathk-tuple dominating set problem on unit disk graphs. On the hardness side, we show a Ω(n2) bits lower bound for the space complexity of any (randomized) streaming algorithm for Liar's dominating set problem as well as for the \boldmathk-tuple dominating set problem. Furthermore, we prove that the Liar's dominating set problem on bipartite graphs is W[2]-hard.