Banerjee, S., & Bhore, S. (2019). Algorithm and Hardness Results on Liar’s Dominating Set and k-tuple Dominating Set. In C. Colbourn, R. Grossi, & N. PISANTI (Eds.), Combinatorial Algorithms - 30th International Workshop IWOCA 2019 (pp. 48–60). LNCS. https://doi.org/10.1007/978-3-030-25005-8_5
International Workshop on Combinatorial Algorithms (IWOCA 2019)
-
Veranstaltungszeitraum:
23-Jul-2019 - 25-Jul-2019
-
Veranstaltungsort:
Pisa, Italien
-
Umfang:
13
-
Verlag:
LNCS, 11638
-
Verlag:
Springer
-
Peer Reviewed:
Ja
-
Abstract:
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: k-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 design a polynomial time approximation scheme (PTAS) for the k-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 k-tuple dominating set problem. Furthermore, we prove that the Liar´s dominating set problem on bipartite graphs is W[2]-hard.
