Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNode-Weighted Network Design in Planar and Minor-Closed Families of Graphs
147
0
0.0
(
0
)
Added by
Ali Vakilian
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We consider node-weighted survivable network design (SNDP) in planar graphs and minor-closed families of graphs. The input consists of a node-weighted undirected graph $G=(V,E)$ and integer connectivity requirements $r(uv)$ for each unordered pair of nodes $uv$. The goal is to find a minimum weighted subgraph $H$ of $G$ such that $H$ contains $r(uv)$ disjoint paths between $u$ and $v$ for each node pair $uv$. Thr
rate research
Read More
We study the problem of finding a minimum weight connected subgraph spanning at least $k$ vertices on planar, node-weighted graphs. We give a $(4+eps)$-approximation algorithm for this problem. We achieve this by utilizing the recent LMP primal-dual $3$-approximation for the node-weighted prize-collecting Steiner tree problem by Byrka et al (SWAT16) and adopting an approach by Chudak et al. (Math. Prog. 04) regarding Lagrangian relaxation for the edge-weighted variant. In particular, we improve the procedure of picking additional vertices (tree merging procedure) given by Sadeghian (2013) by taking a constant number of recursive steps and utilizing the limited guessing procedure of Arora and Karakostas (Math. Prog. 06). More generally, our approach readily gives a $( icefrac{4}{3}cdot r+eps)$-approximation on any graph class where the algorithm of Byrka et al. for the prize-collecting version gives an $r$-approximation. We argue that this can be interpreted as a generalization of an analogous result by Konemann et al. (Algorithmica~11) for partial cover problems. Together with a lower bound construction by Mestre (STACS08) for partial cover this implies that our bound is essentially best possible among algorithms that utilize an LMP algorithm for the Lagrangian relaxation as a black box. In addition to that, we argue by a more involved lower bound construction that even using the LMP algorithm by Byrka et al. in a emph{non-black-box} fashion could not beat the factor $ icefrac{4}{3}cdot r$ when the tree merging step relies only on the solutions output by the LMP algorithm.
We study the prize-collecting version of the Node-weighted Steiner Tree problem (NWPCST) restricted to planar graphs. We give a new primal-dual Lagrangian-multiplier-preserving (LMP) 3-approximation algorithm for planar NWPCST. We then show a ($2.88 + epsilon$)-approximation which establishes a new best approximation guarantee for planar NWPCST. This is done by combining our LMP algorithm with a threshold rounding technique and utilizing the 2.4-approximation of Berman and Yaroslavtsev for the version without penalties. We also give a primal-dual 4-approximation algorithm for the more general forest version using techniques introduced by Hajiaghay and Jain.
We study the classical Node-Disjoint Paths (NDP) problem: given an $n$-vertex graph $G$ and a collection $M={(s_1,t_1),ldots,(s_k,t_k)}$ of pairs of vertices of $G$ called demand pairs, find a maximum-cardinality set of node-disjoint paths connecting the demand pairs. NDP is one of the most basic routing problems, that has been studied extensively. Despite this, there are still wide gaps in our understanding of its approximability: the best currently known upper bound of $O(sqrt n)$ on its approximation ratio is achieved via a simple greedy algorithm, while the best current negative result shows that the problem does not have a better than $Omega(log^{1/2-delta}n)$-approximation for any constant $delta$, under standard complexity assumptions. Even for planar graphs no better approximation algorithms are known, and to the best of our knowledge, the best negative bound is APX-hardness. Perhaps the biggest obstacle to obtaining better approximation algorithms for NDP is that most currently known approximation algorithms for this type of problems rely on the standard multicommodity flow relaxation, whose integrality gap is $Omega(sqrt n)$ for NDP, even in planar graphs. In this paper, we break the barrier of $O(sqrt n)$ on the approximability of the NDP problem in planar graphs and obtain an $tilde O(n^{9/19})$-approximation. We introduce a new linear programming relaxation of the problem, and a number of new techniques, that we hope will be helpful in designing more powerful algorithms for this and related problems.
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.
The asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. In this paper, we study the asymptotic dimension of metric spaces generated by graphs and their shortest path metric and show their applications to some continuous spaces. The asymptotic dimension of such graph metrics can be seen as a large scale generalisation of weak diameter network decomposition which has been extensively studied in computer science. We prove that every proper minor-closed family of graphs has asymptotic dimension at most 2, which gives optimal answers to a question of Fujiwara and Papasoglu and (in a strong form) to a problem raised by Ostrovskii and Rosenthal on minor excluded groups. For some special minor-closed families, such as the class of graphs embeddable in a surface of bounded Euler genus, we prove a stronger result and apply this to show that complete Riemannian surfaces have Assouad-Nagata dimension at most 2. Furthermore, our techniques allow us to prove optimal results for the asymptotic dimension of graphs of bounded layered treewidth and graphs of polynomial growth, which are graph classes that are defined by purely combinatorial notions and properly contain graph classes with some natural topological and geometric flavours.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
