Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial Space
105
0
0.0
(
0
)
Added by
Tanmay Inamdar
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
De Berg et al. in [SICOMP 2020] gave an algorithmic framework for subexponential algorithms on geometric graphs with tight (up to ETH) running times. This framework is based on dynamic programming on graphs of weighted treewidth resulting in algorithms that use super-polynomial space. We introduce the notion of weighted treedepth and use it to refine the framework of de Berg et al. for obtaining polynomial space (with tight running times) on geometric graphs. As a result, we prove that for any fixed dimension $d ge 2$ on intersection graphs of similarly-sized fat objects many well-known graph problems including Independent Set, $r$-Dominating Set for constant $r$, Cycle Cover, Hamiltonian Cycle, Hamiltonian Path, Steiner Tree, Connected Vertex Cover, Feedback Vertex Set, and (Connected) Odd Cycle Transversal are solvable in time $2^{O(n^{1-1/d})}$ and within polynomial space.
rate research
Read More
The problem of graph Reachability is to decide whether there is a path from one vertex to another in a given graph. In this paper, we study the Reachability problem on three distinct graph families - intersection graphs of Jordan regions, unit contact disk graphs (penny graphs), and chordal graphs. For each of these graph families, we present space-efficient algorithms for the Reachability problem. For intersection graphs of Jordan regions, we show how to obtain a good vertex separator in a space-efficient manner and use it to solve the Reachability in polynomial time and $O(m^{1/2}log n)$ space, where $n$ is the number of Jordan regions, and $m$ is the total number of crossings among the regions. We use a similar approach for chordal graphs and obtain a polynomial-time and $O(m^{1/2}log n)$ space algorithm, where $n$ and $m$ are the number of vertices and edges, respectively. However, we use a more involved technique for unit contact disk graphs (penny graphs) and obtain a better algorithm. We show that for every $epsilon> 0$, there exists a polynomial-time algorithm that can solve Reachability in an $n$ vertex directed penny graph, using $O(n^{1/4+epsilon})$ space. We note that the method used to solve penny graphs does not extend naturally to the class of geometric intersection graphs that include arbitrary size cliques.
Efficient algorithms are presented for constructing spanners in geometric intersection graphs. For a unit ball graph in R^k, a (1+epsilon)-spanner is obtained using efficient partitioning of the space into hypercubes and solving bichromatic closest pair problems. The spanner construction has almost equivalent complexity to the construction of Euclidean minimum spanning trees. The results are extended to arbitrary ball graphs with a sub-quadratic running time. For unit ball graphs, the spanners have a small separator decomposition which can be used to obtain efficient algorithms for approximating proximity problems like diameter and distance queries. The results on compressed quadtrees, geometric graph separators, and diameter approximation might be of independent interest.
Let $mathcal{D}$ be a set of $n$ disks in the plane. The disk graph $G_mathcal{D}$ for $mathcal{D}$ is the undirected graph with vertex set $mathcal{D}$ in which two disks are joined by an edge if and only if they intersect. The directed transmission graph $G^{rightarrow}_mathcal{D}$ for $mathcal{D}$ is the directed graph with vertex set $mathcal{D}$ in which there is an edge from a disk $D_1 in mathcal{D}$ to a disk $D_2 in mathcal{D}$ if and only if $D_1$ contains the center of $D_2$. Given $mathcal{D}$ and two non-intersecting disks $s, t in mathcal{D}$, we show that a minimum $s$-$t$ vertex cut in $G_mathcal{D}$ or in $G^{rightarrow}_mathcal{D}$ can be found in $O(n^{3/2}text{polylog} n)$ expected time. To obtain our result, we combine an algorithm for the maximum flow problem in general graphs with dynamic geometric data structures to manipulate the disks. As an application, we consider the barrier resilience problem in a rectangular domain. In this problem, we have a vertical strip $S$ bounded by two vertical lines, $L_ell$ and $L_r$, and a collection $mathcal{D}$ of disks. Let $a$ be a point in $S$ above all disks of $mathcal{D}$, and let $b$ a point in $S$ below all disks of $mathcal{D}$. The task is to find a curve from $a$ to $b$ that lies in $S$ and that intersects as few disks of $mathcal{D}$ as possible. Using our improved algorithm for minimum cuts in disk graphs, we can solve the barrier resilience problem in $O(n^{3/2}text{polylog} n)$ expected time.
We show that the k-Dominating Set problem is fixed parameter tractable (FPT) and has a polynomial kernel for any class of graphs that exclude K_{i,j} as a subgraph, for any fixed i, j >= 1. This strictly includes every class of graphs for which this problem has been previously shown to have FPT algorithms and/or polynomial kernels. In particular, our result implies that the problem restricted to bounded- degenerate graphs has a polynomial kernel, solving an open problem posed by Alon and Gutner.
Let $A$ and $B$ be two point sets in the plane of sizes $r$ and $n$ respectively (assume $r leq n$), and let $k$ be a parameter. A matching between $A$ and $B$ is a family of pairs in $A times B$ so that any point of $A cup B$ appears in at most one pair. Given two positive integers $p$ and $q$, we define the cost of matching $M$ to be $c(M) = sum_{(a, b) in M}|{a-b}|_p^q$ where $|{cdot}|_p$ is the $L_p$-norm. The geometric partial matching problem asks to find the minimum-cost size-$k$ matching between $A$ and $B$. We present efficient algorithms for geometric partial matching problem that work for any powers of $L_p$-norm matching objective: An exact algorithm that runs in $O((n + k^2) {mathop{mathrm{polylog}}} n)$ time, and a $(1 + varepsilon)$-approximation algorithm that runs in $O((n + ksqrt{k}) {mathop{mathrm{polylog}}} n cdot logvarepsilon^{-1})$ time. Both algorithms are based on the primal-dual flow augmentation scheme; the main improvements involve using dynamic data structures to achieve efficient flow augmentations. With similar techniques, we give an exact algorithm for the planar transportation problem running in $O(min{n^2, rn^{3/2}} {mathop{mathrm{polylog}}} n)$ time.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
