Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLocal Approximability of Minimum Dominating Set on Planar Graphs
208
0
0.0
(
0
)
Added by
Jukka Suomela
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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$.
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 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.
In the problem of minimum connected dominating set with routing cost constraint, we are given a graph $G=(V,E)$, and the goal is to find the smallest connected dominating set $D$ of $G$ such that, for any two non-adjacent vertices $u$ and $v$ in $G$, the number of internal nodes on the shortest path between $u$ and $v$ in the subgraph of $G$ induced by $D cup {u,v}$ is at most $alpha$ times that in $G$. For general graphs, the only known previous approximability result is an $O(log n)$-approximation algorithm ($n=|V|$) for $alpha = 1$ by Ding et al. For any constant $alpha > 1$, we give an $O(n^{1-frac{1}{alpha}}(log n)^{frac{1}{alpha}})$-approximation algorithm. When $alpha geq 5$, we give an $O(sqrt{n}log n)$-approximation algorithm. Finally, we prove that, when $alpha =2$, unless $NP subseteq DTIME(n^{polylog n})$, for any constant $epsilon > 0$, the problem admits no polynomial-time $2^{log^{1-epsilon}n}$-approximation algorithm, improving upon the $Omega(log n)$ bound by Du et al. (albeit under a stronger hardness assumption).
Naor, Parter, and Yogev (SODA 2020) have recently demonstrated the existence of a emph{distributed interactive proof} for planarity (i.e., for certifying that a network is planar), using a sophisticated generic technique for constructing distributed IP protocols based on sequential IP protocols. The interactive proof for planarity is based on a distributed certification of the correct execution of any given sequential linear-time algorithm for planarity testing. It involves three interactions between the prover and the randomized distributed verifier (i.e., it is a dMAM/ protocol), and uses small certificates, on $O(log n)$ bits in $n$-node networks. We show that a single interaction from the prover suffices, and randomization is unecessary, by providing an explicit description of a emph{proof-labeling scheme} for planarity, still using certificates on just $O(log n)$ bits. We also show that there are no proof-labeling schemes -- in fact, even no emph{locally checkable proofs} -- for planarity using certificates on $o(log n)$ bits.
We study a family of generalizations of Edge Dominating Set on directed graphs called Directed $(p,q)$-Edge Dominating Set. In this problem an arc $(u,v)$ is said to dominate itself, as well as all arcs which are at distance at most $q$ from $v$, or at distance at most $p$ to $u$. First, we give significantly improved FPT algorithms for the two most important cases of the problem, $(0,1)$-dEDS and $(1,1)$-dEDS (that correspond
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
