Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA tight local algorithm for the minimum dominating set problem in outerplanar graphs
149
0
0.0
(
0
)
Added by
Carla Groenland
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We show that there is a deterministic local algorithm (constant-time distributed graph algorithm) that finds a 5-approximation of a minimum dominating set on outerplanar graphs. We show there is no such algorithm that finds a $(5-varepsilon)$-approximation, for any $varepsilon>0$. Our algorithm only requires knowledge of the degree of a vertex and of its neighbors, so that large messages and unique identifiers are not needed.
rate research
Read More
The Minimum Dominating Set (MDS) problem is not only one of the most fundamental problems in distributed computing, it is also one of the most challenging ones. While it is well-known that minimum dominating sets cannot be approximated locally on general graphs, over the last years, several breakthroughs have been made on computing local approximations on sparse graphs. This paper presents a deterministic and local constant factor approximation for minimum dominating sets on bounded genus graphs, a very large family of sparse graphs. Our main technical contribution is a new analysis of a slightly modified, first-order definable variant of an existing algorithm by Lenzen et al. Interestingly, unlike existing proofs for planar graphs, our analysis does not rely on any topological arguments. We believe that our techniques can be useful for the study of local problems on sparse graphs beyond the scope of this paper.
We show that there is no deterministic local algorithm (constant-time distributed graph algorithm) that finds a $(7-epsilon)$-approximation of a minimum dominating set on planar graphs, for any positive constant $epsilon$. In prior work, the best lower bound on the approximation ratio has been $5-epsilon$; there is also an upper bound of $52$.
Given a graph $G=(V,E)$ and an integer $k ge 1$, a $k$-hop dominating set $D$ of $G$ is a subset of $V$, such that, for every vertex $v in V$, there exists a node $u in D$ whose hop-distance from $v$ is at most $k$. A $k$-hop dominating set of minimum cardinality is called a minimum $k$-hop dominating set. In this paper, we present linear-time algorithms that find a minimum $k$-hop dominating set in unicyclic and cactus graphs. To achieve this, we show that the $k$-dominating set problem on unicycle graph reduces to the piercing circular arcs problem, and show a linear-time algorithm for piercing sorted circular arcs, which improves the best known $O(nlog n)$-time algorithm.
We completely determine the complexity status of the dominating set problem for hereditary graph classes defined by forbidden induced subgraphs with at most five vertices.
Given a graph $G=(V,E)$, the dominating set problem asks for a minimum subset of vertices $Dsubseteq V$ such that every vertex $uin Vsetminus D$ is adjacent to at least one vertex $vin D$. That is, the set $D$ satisfies the condition that $|N[v]cap D|geq 1$ for each $vin V$, where $N[v]$ is the closed neighborhood of $v$. In this paper, we study two variants of the classical dominating set problem: $boldmath{k}$-tuple dominating set ($k$-DS) problem and Liars dominating set (LDS) problem, and obtain several algorithmic and hardness results. On the algorithmic side, we present a constant factor ($frac{11}{2}$)-approximation algorithm for the Liars dominating set problem on unit disk graphs. Then, we obtain a PTAS for the $boldmath{k}$-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 Liars dominating set problem as well as for the $boldmath{k}$-tuple dominating set problem. Furthermore, we prove that the Liars dominating set problem on bipartite graphs is W[2]-hard.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
