Algorithm and hardness results on liar's dominating set and k-tuple dominating set

DOI10.1007/978-3-030-25005-8_5MaRDI QIDQ2301734zbMATH OpenOpenAlexFDO

Authors Sandip Banerjee, Sujoy Bhore

Publication date 25 February 2020

Full work available at URL https://arxiv.org/abs/1902.11149

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Abstract: Given a graph $G=(V,E)$, the dominating set problem asks for a minimum subset of vertices $DsubseteqV$ such that every vertex $uinVsetminusD$ is adjacent to at least one vertex $vinD$. That is, the set $D$ satisfies the condition that $|N[v]capD|geq1$ for each $vinV$, where $N[v]$ is the closed neighborhood of $v$. In this paper, we study two variants of the classical dominating set problem: $$-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 ($frac112$)-approximation algorithm for the Liar's dominating set problem on unit disk graphs. Then, we obtain a PTAS for the $$-tuple dominating set problem on unit disk graphs. On the hardness side, we show a $Omega(n^2)$ bits lower bound for the space complexity of any (randomized) streaming algorithm for Liar's dominating set problem as well as for the $$-tuple dominating set problem. Furthermore, we prove that the Liar's dominating set problem on bipartite graphs is W[2]-hard.

Recommendations

• Liar's dominating set in unit disk graphs
• Liar's domination in unit disk graphs
• Hardness results, approximation and exact algorithms for liar's domination problem in graphs
• Liar's dominating set problem on unit disk graphs
• Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs

Cited in

(7)

• Liar's dominating set problem on unit disk graphs
• Liar's domination in unit disk graphs
• Hardness results, approximation and exact algorithms for liar's domination problem in graphs
• Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs
• Liar's domination in 2D
• Statistical mechanics of the directed 2-distance minimal dominating set problem
• Balanced independent and dominating sets on colored interval graphs

This page was built for publication: Algorithm and hardness results on liar's dominating set and \({k}\)-tuple dominating set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2301734)