Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs
169
0
0.0
(
0
)
Added by
Hung Le
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Understanding the structure of minor-free metrics, namely shortest path metrics obtained over a weighted graph excluding a fixed minor, has been an important research direction since the fundamental work of Robertson and Seymour. A fundamental idea that helps both to understand the structural properties of these metrics and lead to strong algorithmic results is to construct a small-complexity graph that approximately preserves distances between pairs of points of the metric. We show the two following structural results for minor-free metrics: 1. Construction of a light subset spanner. Given a subset of vertices called terminals, and $epsilon$, in polynomial time we construct a subgraph that preserves all pairwise distances between terminals up to a multiplicative $1+epsilon$ factor, of total weight at most $O_{epsilon}(1)$ times the weight of the minimal Steiner tree spanning the terminals. 2. Construction of a stochastic metric embedding into low treewidth graphs with expected additive distortion $epsilon D$. Namely, given a minor free graph $G=(V,E,w)$ of diameter $D$, and parameter $epsilon$, we construct a distribution $mathcal{D}$ over dominating metric embeddings into treewidth-$O_{epsilon}(log n)$ graphs such that the additive distortion is at most $epsilon D$. One of our important technical contributions is a novel framework that allows us to reduce emph{both problems} to problems on simpler graphs of bounded diameter. Our results have the following algorithmic consequences: (1) the first efficient approximation scheme for subset TSP in minor-free metrics; (2) the first approximation scheme for vehicle routing with bounded capacity in minor-free metrics; (3) the first efficient approximation scheme for vehicle routing with bounded capacity on bounded genus metrics.
rate research
Read More
In the Group Steiner Tree problem (GST), we are given a (vertex or edge)-weighted graph $G=(V,E)$ on $n$ vertices, a root vertex $r$ and a collection of groups ${S_i}_{iin[h]}: S_isubseteq V(G)$. The goal is to find a min-cost subgraph $H$ that connects the root to every group. We consider a fault-tolerant variant of GST, which we call Restricted (Rooted) Group SNDP. In this setting, each group $S_i$ has a demand $k_iin[k],kinmathbb N$, and we wish to find a min-cost $Hsubseteq G$ such that, for each group $S_i$, there is a vertex in $S_i$ connected to the root via $k_i$ (vertex or edge) disjoint paths. While GST admits $O(log^2 nlog h)$ approximation, its high connectivity variants are Label-Cover hard, and for the vertex-weighted version, the hardness holds even when $k=2$. Previously, positive results were known only for the edge-weighted version when $k=2$ [Gupta et al., SODA 2010; Khandekar et al., Theor. Comput. Sci., 2012] and for a relaxed variant where the disjoint paths may end at different vertices in a group [Chalermsook et al., SODA 2015]. Our main result is an $O(log nlog h)$ approximation for Restricted Group SNDP that runs in time $n^{f(k, w)}$, where $w$ is the treewidth of $G$. This nearly matches the lower bound when $k$ and $w$ are constant. The key to achieving this result is a non-trivial extension of the framework in [Chalermsook et al., SODA 2017], which embeds all feasible solutions to the problem into a dynamic program (DP) table. However, finding the optimal solution in the DP table remains intractable. We formulate a linear program relaxation for the DP and obtain an approximate solution via randomized rounding. This framework also allows us to systematically construct DP tables for high-connectivity problems. As a result, we present new exact algorithms for several variants of survivable network design problems in low-treewidth graphs.
We study the problem of embedding graphs in the plane as good geometric spanners. That is, for a graph $G$, the goal is to construct a straight-line drawing $Gamma$ of $G$ in the plane such that, for any two vertices $u$ and $v$ of $G$, the ratio between the minimum length of any path from $u$ to $v$ and the Euclidean distance between $u$ and $v$ is small. The maximum such ratio, over all pairs of vertices of $G$, is the spanning ratio of $Gamma$. First, we show that deciding whether a graph admits a straight-line drawing with spanning ratio $1$, a proper straight-line drawing with spanning ratio $1$, and a planar straight-line drawing with spanning ratio $1$ are NP-complete, $exists mathbb R$-complete, and linear-time solvable problems, respectively, where a drawing is proper if no two vertices overlap and no edge overlaps a vertex. Second, we show that moving from spanning ratio $1$ to spanning ratio $1+epsilon$ allows us to draw every graph. Namely, we prove that, for every $epsilon>0$, every (planar) graph admits a proper (resp. planar) straight-line drawing with spanning ratio smaller than $1+epsilon$. Third, our drawings with spanning ratio smaller than $1+epsilon$ have large edge-length ratio, that is, the ratio between the length of the longest edge and the length of the shortest edge is exponential. We show that this is sometimes unavoidable. More generally, we identify having bounded toughness as the criterion that distinguishes graphs that admit straight-line drawings with constant spanning ratio and polynomial edge-length ratio from graphs that require exponential edge-length ratio in any straight-line drawing with constant spanning ratio.
In the literature on parameterized graph problems, there has been an increased effort in recent years aimed at exploring novel notions of graph edit-distance that are more powerful than the size of a modulator to a specific graph class. In this line of research, Bulian and Dawar [Algorithmica, 2016] introduced the notion of elimination distance and showed that deciding whether a given graph has elimination distance at most $k$ to any minor-closed class of graphs is fixed-parameter tractable parameterized by $k$ [Algorithmica, 2017]. There has been a subsequent series of results on the fixed-parameter tractability of elimination distance to various graph classes. However, one class of graph classes to which the computation of elimination distance has remained open is the class of graphs that are characterized by the exclusion of a family ${cal F}$ of finite graphs as topological minors. In this paper, we settle this question by showing that the problem of determining elimination distance to such graphs is also fixed-parameter tractable.
Let $M=(m_{ij})$ be a symmetric matrix of order $n$ whose elements lie in an arbitrary field $mathbb{F}$, and let $G$ be the graph with vertex set ${1,ldots,n}$ such that distinct vertices $i$ and $j$ are adjacent if and only if $m_{ij} eq 0$. We introduce a dynamic programming algorithm that finds a diagonal matrix that is congruent to $M$. If $G$ is given with a tree decomposition $mathcal{T}$ of width $k$, then this can be done in time $O(k|mathcal{T}| + k^2 n)$, where $|mathcal{T}|$ denotes the number of nodes in $mathcal{T}$. Among other things, this allows one to compute the determinant, the rank and the inertia of a symmetric matrix in time $O(k|mathcal{T}| + k^2 n)$.
A (1 + eps)-approximate distance oracle for a graph is a data structure that supports approximate point-to-point shortest-path-distance queries. The most relevant measures for a distance-oracle construction are: space, query time, and preprocessing time. There are strong distance-oracle constructions known for planar graphs (Thorup, JACM04) and, subsequently, minor-excluded graphs (Abraham and Gavoille, PODC06). However, these require Omega(eps^{-1} n lg n) space for n-node graphs. We argue that a very low space requirement is essential. Since modern computer architectures involve hierarchical memory (caches, primary memory, secondary memory), a high memory requirement in effect may greatly increase the actual running time. Moreover, we would like data structures that can be deployed on small mobile devices, such as handhelds, which have relatively small primary memory. In this paper, for planar graphs, bounded-genus graphs, and minor-excluded graphs we give distance-oracle constructions that require only O(n) space. The big O hides only a fixed constant, independent of epsilon and independent of genus or size of an excluded minor. The preprocessing times for our distance oracle are also faster than those for the previously known constructions. For planar graphs, the preprocessing time is O(n lg^2 n). However, our constructions have slower query times. For planar graphs, the query time is O(eps^{-2} lg^2 n). For our linear-space results, we can in fact ensure, for any delta > 0, that the space required is only 1 + delta times the space required just to represent the graph itself.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
