Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAlgorithm and Hardness results on Liars Dominating Set and $k$-tuple Dominating Set
146
0
0.0
(
0
)
Added by
Sujoy Bhore
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We recently introduced the graph invariant twin-width, and showed that first-order model checking can be solved in time $f(d,k)n$ for $n$-vertex graphs given with a witness that the twin-width is at most $d$, called $d$-contraction sequence or $d$-sequence, and formulas of size $k$ [Bonnet et al., FOCS 20]. The inevitable price to pay for such a general result is that $f$ is a tower of exponentials of height roughly $k$. In this paper, we show that algorithms based on twin-width need not be impractical. We present $2^{O(k)}n$-time algorithms for $k$-Independent Set, $r$-Scattered Set, $k$-Clique, and $k$-Dominating Set when an $O(1)$-sequence is provided. We further show how to solve weighted $k$-Independent Set, Subgraph Isomorphism, and Induced Subgraph Isomorphism, in time $2^{O(k log k)}n$. These algorithms are based on a dynamic programming scheme following the sequence of contractions forward. We then show a second algorithmic use of the contraction sequence, by starting at its end and rewinding it. As an example, we establish that bounded twin-width classes are $chi$-bounded. This significantly extends the $chi$-boundedness of bounded rank-width classes, and does so with a very concise proof. The third algorithmic use of twin-width builds on the second one. Playing the contraction sequence backward, we show that bounded twin-width graphs can be edge-partitioned into a linear number of bicliques, such that both sides of the bicliques are on consecutive vertices, in a fixed vertex ordering. Given that biclique edge-partition, we show how to solve the unweighted Single-Source Shortest Paths and hence All-Pairs Shortest Paths in sublinear time $O(n log n)$ and time $O(n^2 log n)$, respectively. Finally we show that Min Dominating Set and related problems have constant integrality gaps on bounded twin-width classes, thereby getting constant approximations on these classes.
In this paper, we study two classic optimization problems: minimum geometric dominating set and set cover. Both the problems have been studied for different types of objects for a long time. These problems become APX-hard when the objects are axis-parallel rectangles, ellipses, $alpha$-fat objects of constant description complexity, and convex polygons. On the other hand, PTAS (polynomial time approximation scheme) is known for them when the objects are disks or unit squares. Surprisingly, PTAS was unknown even for arbitrary squares. For homothetic set of convex objects, an $O(k^4)$ approximation algorithm is known for dominating set problem, where $k$ is the number of corners in a convex object. On the other hand, QPTAS (quasi polynomial time approximation scheme) is known very recently for the covering problem when the objects are pseudodisks. For both problems obtaining a PTAS remains open for a large class of objects. For the dominating set problems, we prove that the popular local search algorithm leads to an $(1+varepsilon)$ approximation when objects are homothetic set of convex objects (which includes arbitrary squares, $k$-regular polygons, translated and scaled copies of a convex set etc.) in $n^{O(1/varepsilon^2)}$ time. On the other hand, the same technique leads to a PTAS for geometric covering problem when the objects are convex pseudodisks (which includes disks, unit height rectangles, homothetic convex objects etc.). As a consequence, we obtain an easy to implement approximation algorithm for both problems for a large class of objects, significantly improving the best known approximation guarantees.
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
This paper is devoted to the online dominating set problem and its variants. We believe the paper represents the first systematic study of the effect of two limitations of online algorithms: making irrevocable decisions while not knowing the future, and being incremental, i.e., having to maintain solutions to all prefixes of the input. This is quantified through competitive analyses of online algorithms against two optimal algorithms, both knowing the entire input, but only one having to be incremental. We also consider the competitive ratio of the weaker of the two optimal algorithms against the other. We consider important graph classes, distinguishing between connected and not necessarily connected graphs. For the classic graph classes of trees, bipartite, planar, and general graphs, we obtain tight results in almost all cases. We also derive upper and lower bounds for the class of bounded-degree graphs. From these analyses, we get detailed information regarding the significance of the necessary requirement that online algorithms be incremental. In some cases, having to be incremental fully accounts for the online algorithms disadvantage.
In this article, we study a generalized version of the maximum independent set and minimum dominating set problems, namely, the maximum $d$-distance independent set problem and the minimum $d$-distance dominating set problem on unit disk graphs for a positive integer $d>0$. We first show that the maximum $d$-distance independent set problem and the minimum $d$-distance dominating set problem belongs to NP-hard class. Next, we propose a simple polynomial-time constant-factor approximation algorithms and PTAS for both the problems.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
