We consider nodeweighted survivable network design (SNDP) in planar graphs and minorclosed families of graphs. The input consists of a nodeweighted 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 . Three versions of the problem are edgeconnectivity SNDP (ECSNDP), elementconnectivity SNDP (ElemSNDP), and vertexconnectivity SNDP (VCSNDP), depending on whether the paths are required to be edge, element, or vertex disjoint, respectively. Our main result is an O ( k )approximation algorithm for ECSNDP and ElemSNDP when the input graph is planar or more generally if it belongs to a proper minorclosed family of graphs; here, k = max uv r ( uv ) is the maximum connectivity requirement. This improves upon the O ( k log n )approximation known for nodeweighted ECSNDP and ElemSNDP in general graphs [31]. We also obtain an O (1) approximation for nodeweighted VCSNDP when the connectivity requirements are in {0, 1, 2}; for higher connectivity our resultmore »
Tree embeddings for hopconstrained network design
Network design problems aim to compute lowcost structures such as routes, trees and subgraphs. Often, it is natural and desirable to require that these structures have small hop length or hop diameter. Unfortunately, optimization problems with hop constraints are much harder and less well understood than their hopunconstrained counterparts. A significant algorithmic barrier in this setting is the fact that hopconstrained distances in graphs are very far from being a metric.
We show that, nonetheless, hopconstrained distances can be approximated by distributions over ``partial tree metrics.'' We build this result into a powerful and versatile algorithmic tool which, similarly to classic probabilistic tree embeddings, reduces hopconstrained problems in general graphs to hopunconstrained problems on trees. We then use this tool to give the first polylogarithmic bicriteria approximations for the hopconstrained variants of many classic network design problems. These include Steiner forest, group Steiner tree, group Steiner forest, buyatbulk network design as well as online and oblivious versions of many of these problems.
 Publication Date:
 NSFPAR ID:
 10271617
 Journal Name:
 Symposium on Theory of Computing (STOC)
 Page Range or eLocationID:
 356 to 369
 Sponsoring Org:
 National Science Foundation
More Like this


Understanding the structure of minorfree 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 “smallcomplexity” graph that approximately preserves distances between pairs of points of the metric. We show the two following structural results for minorfree metrics: 1) Construction of a light subset spanner. Given a subset of vertices called terminals, and ϵ, in polynomial time we construct a sub graph that preserves all pairwise distances between terminals up to a multiplicative 1+ϵ factor, of total weight at most Oϵ(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 ϵD. Namely, given a minorfree graph G=(V,E,w) of diameter D, and parameter ϵ, we construct a distribution D over dominating metric embeddings into treewidthOϵ(log n) graphs such that ∀u,v∈V, Ef∼D[dH(f(u),f(v))]≤dG(u,v)+ϵD. Our results have the following algorithmic consequences: (1) the first efficient approximation scheme for subset TSP in minorfree metrics; (2) themore »

Given two points s and t in the plane and a set of obstacles defined by closed curves, what is the minimum number of obstacles touched by a path connecting s and t? This is a fundamental and wellstudied problem arising naturally in computational geometry, graph theory (under the names MinColor Path and Minimum Label Path), wireless sensor networks (Barrier Resilience) and motion planning (Minimum Constraint Removal). It remains NPhard even for very simpleshaped obstacles such as unitlength line segments. In this paper we give the first constant factor approximation algorithm for this problem, resolving an open problem of [Chan and Kirkpatrick, TCS, 2014] and [Bandyapadhyay et al., CGTA, 2020]. We also obtain a constant factor approximation for the Minimum Color Prize Collecting Steiner Forest where the goal is to connect multiple request pairs (s1, t1), . . . , (sk, tk) while minimizing the number of obstacles touched by any (si, ti) path plus a fixed cost of wi for each pair (si, ti) left disconnected. This generalizes the classic Steiner Forest and PrizeCollecting Steiner Forest problems on planar graphs, for which intricate PTASes are known. In contrast, no PTAS is possible for MinColor Path even on planar graphsmore »

Network disaster recovery is one of the greatest concerns for Mobile Network Operators (MNOs) and first responders during largescale natural disasters such as earth quakes. In many recent studies, wireless multihop networking has been demonstrated as an effective technique to quickly and efficiently extend the network coverage during disasters. In this paper, we specifically address the network deployment problem by proposing the PopulationAware Relay Placement (PARP) solution, which seeks the efficient deployment of a limited number of relays such that population coverage is maximized in the scenario of network disaster recovery. We provide a graphbased modeling and prove its NPhardness accordingly. In order to efficiently solve this problem, we propose a heuristic solution, which is constructed in two steps. We first design a simple algorithm based on a disk graph to determine the Steiner locations, which is the biggest challenge in this problem. Then, we formulate the problem as an integer programming problem, which is inspired by the formulation of PrizeCollecting Steiner Tree (PCST). Thus, the integer problem is solved by exploring the similarity of the existing algorithm for PCST. To evaluate the proposed solution extensively, we present numerical results on both realworld and random scenarios, which validate the effectivenessmore »

We consider the following general network design problem on directed graphs. The input is an asymmetric metric (V, c), root r in V, monotone submodular function f and budget B. The goal is to find an rrooted arborescence T of cost at most B that maximizes f(T). Our main result is a very simple quasipolynomial time approximation algorithm for this problem, where k ≤ V is the number of vertices in an optimal solution. To the best of our knowledge, this is the first nontrivial approximation ratio for this problem. As a consequence we obtain an O(log^2 k / loglog k) approximation algorithm for directed (polymatroid) Steiner tree in quasipolynomial time. We also extend our main result to a setting with additional length bounds at vertices, which leads to improved approximation algorithms for the singlesource buyatbulk and priority Steiner tree problems. For the usual directed Steiner tree problem, our result matches the best previous approximation ratio, but improves significantly on the running time. For polymatroid Steiner tree and singlesource buyatbulk, our result improves prior approximation ratios by a logarithmic factor. For directed priority Steiner tree, our result seems to be the first nontrivial approximation ratio. Under certain complexity assumptions, ourmore »