Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFinding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs
160
0
0.0
(
0
)
Added by
Fahad Panolan
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We give algorithms with running time $2^{O({sqrt{k}log{k}})} cdot n^{O(1)}$ for the following problems. Given an $n$-vertex unit disk graph $G$ and an integer $k$, decide whether $G$ contains (1) a path on exactly/at least $k$ vertices, (2) a cycle on exactly $k$ vertices, (3) a cycle on at least $k$ vertices, (4) a feedback vertex set of size at most $k$, and (5) a set of $k$ pairwise vertex-disjoint cycles. For the first three problems, no subexponential time parameterized algorithms were previously known. For the remaining two problems, our algorithms significantly outperform the previously best known parameterized algorithms that run in time $2^{O(k^{0.75}log{k})} cdot n^{O(1)}$. Our algorithms are based on a new kind of tree decompositions of unit disk graphs where the separators can have size up to $k^{O(1)}$ and there exists a solution that crosses every separator at most $O(sqrt{k})$ times. The running times of our algorithms are optimal up to the $log{k}$ factor in the exponent, assuming the Exponential Time Hypothesis.
rate research
Read More
Let $G=(V,E)$ be an undirected graph. We call $D_t subseteq V$ as a total dominating set (TDS) of $G$ if each vertex $v in V$ has a dominator in $D$ other than itself. Here we consider the TDS problem in unit disk graphs, where the objective is to find a minimum cardinality total dominating set for an input graph. We prove that the TDS problem is NP-hard in unit disk graphs. Next, we propose an 8-factor approximation algorithm for the problem. The running time of the proposed approximation algorithm is $O(n log k)$, where $n$ is the number of vertices of the input graph and $k$ is output size. We also show that TDS problem admits a PTAS in unit disk graphs.
Greedy routing has been studied successfully on Euclidean unit disk graphs, which we interpret as a special case of hyperbolic unit disk graphs. While sparse Euclidean unit disk graphs exhibit grid-like structure, we introduce strongly hyperbolic unit disk graphs as the natural counterpart containing graphs that have hierarchical network structures. We develop and analyze a routing scheme that utilizes these hierarchies. On arbitrary graphs this scheme guarantees a worst case stretch of $max{3, 1+2b/a}$ for $a > 0$ and $b > 1$. Moreover, it stores $mathcal{O}(k(log^2{n} + log{k}))$ bits at each vertex and takes $mathcal{O}(k)$ time for a routing decision, where $k = pi e (1 + a)/(2(b - 1)) (b^2 text{diam}(G) - 1) R + log_b(text{diam}(G)) + 1$, on strongly hyperbolic unit disk graphs with threshold radius $R > 0$. In particular, for hyperbolic random graphs, which have previously been used to model hierarchical networks like the internet, $k = mathcal{O}(log^2{n})$ holds asymptotically almost surely. Thus, we obtain a worst-case stretch of $3$, $mathcal{O}(log^4 n)$ bits of storage per vertex, and $mathcal{O}(log^2 n)$ time per routing decision on such networks. This beats existing worst-case lower bounds. Our proof of concept implementation indicates that the obtained results translate well to real-world networks.
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.
We study the algorithmic properties of the graph class Chordal-ke, that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fill-in at most k. We discover that a number of fundamental intractable optimization problems being parameterized by k admit subexponential algorithms on graphs from Chordal-ke. We identify a large class of optimization problems on Chordal-ke that admit algorithms with the typical running time 2^{O(sqrt{k}log k)}cdot n^{O(1)}. Examples of the problems from this class are finding an independent set of maximum weight, finding a feedback vertex set or an odd cycle transversal of minimum weight, or the problem of finding a maximum induced planar subgraph. On the other hand, we show that for some fundamental optimization problems, like finding an optimal graph coloring or finding a maximum clique, are FPT on Chordal-ke when parameterized by k but do not admit subexponential in k algorithms unless ETH fails. Besides subexponential time algorithms, the class of Chordal-ke graphs appears to be appealing from the perspective of kernelization (with parameter k). While it is possible to show that most of the weighted variants of optimization problems do not admit polynomial in k kernels on Chordal-ke graphs, this does not exclude the existence of Turing kernelization and kernelization for unweighted graphs. In particular, we construct a polynomial Turing kernel for Weighted Clique on Chordal-ke graphs. For (unweighted) Independent Set we design polynomial kernels on two interesting subclasses of Chordal-ke, namely, Interval-ke and Split-ke graphs.
Coloring unit-disk graphs efficiently is an important problem in the global and distributed setting, with applications in radio channel assignment problems when the communication relies on omni-directional antennas of the same power. In this context it is important to bound not only the complexity of the coloring algorithms, but also the number of colors used. In this paper, we consider two natural distributed settings. In the location-aware setting (when nodes know their coordinates in the plane), we give a constant time distributed algorithm coloring any unit-disk graph $G$ with at most $(3+epsilon)omega(G)+6$ colors, for any constant $epsilon>0$, where $omega(G)$ is the clique number of $G$. This improves upon a classical 3-approximation algorithm for this problem, for all unit-disk graphs whose chromatic number significantly exceeds their clique number. When nodes do not know their coordinates in the plane, we give a distributed algorithm in the LOCAL model that colors every unit-disk graph $G$ with at most $5.68omega(G)$ colors in $O(2^{sqrt{log log n}})$ rounds. Moreover, when $omega(G)=O(1)$, the algorithm runs in $O(log^* n)$ rounds. This algorithm is based on a study of the local structure of unit-disk graphs, which is of independent interest. We conjecture that every unit-disk graph $G$ has average degree at most $4omega(G)$, which would imply the existence of a $O(log n)$ round algorithm coloring any unit-disk graph $G$ with (approximatively) $4omega(G)$ colors.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
