In this paper, we study a survivable network design problem on directed graphs, 2-Connected Directed Steiner Tree (2-DST): given an @math -vertex weighted directed graph, a root @math , and a set of @math terminals @math , find a min-cost subgraph @math that has two edge vertex disjoint paths from @math to any @math . 2-DST is a natural generalization of the classical Directed Steiner Tree problem (DST), where we have an additional requirement that the network must tolerate one failure. No non-trivial approximation is known for 2-DST. This was left as an open problem by , [SODA'09; JCSS] and has then been studied by [SODA'12; TALG] and Laekhanukit SODA'14]. However, no positive result was known except for the special case of a @math -shallow instance [Laekhanukit, ICALP'16]. We present an @math approximation algorithm for 2-DST that runs in time @math , for any @math . This implies a polynomial-time @math approximation for any constant @math , and a poly-logarithmic approximation running in quasi-polynomial time. We remark that this is essentially the best-known even for the classical DST, and the latter problem is @math -hard to approximate [Halperin and Krauthgamer, STOC'03]. As a by product, we obtain an algorithm with the same approximation guarantee for the @math -Connected Directed Steiner Subgraph problem, where the goal is to find a min-cost subgraph such that every pair of terminals are @math -edge vertex connected.
Concerning vertex connectivity, two of the most well-studied problems are the @math -Vertex Connected Steiner Tree ( @math -ST) and @math -Vertex Connected Steiner Subgraph ( @math -SS) problems, i.e., the undirected versions of and , respectively. There are @math -approximation algorithms for @math -ST and @math -SS by Fleischer et al. @cite_38 using the iterative rounding method. For @math , Nutov devised an @math -approximation algorithm for @math -ST in @cite_32 and an @math -approximation algorithm for @math -SS in @cite_15 (also, see @cite_29 ). A special case of @math -SS with metric-costs is studied by Cheriyan and Vetta in @cite_36 who gave an @math -approximation algorithm for the problem. The most extensively studied special case of @math -SS is when all vertices are terminals, namely the @math -Vertex Connected Spanning Subgraph problem, which has been studied, e.g., in @cite_10 @cite_1 @cite_16 @cite_37 @cite_18 . The current best approximation guarantees are @math @cite_37 , and @math for the case @math @cite_18 @cite_7 . More references can be found in @cite_8 @cite_14 @cite_4 .
@cite_38 @cite_37 @cite_18 @cite_14 @cite_4 @cite_7 @cite_8 @cite_36 @cite_29 @cite_1 @cite_32 @cite_15 @cite_16 @cite_10
2161190897 2943842266 2532977679 2104116126
We present algorithmic and hardness results for network design problems with degree or order constraints. The first problem we consider is the Survivable Network Design problem with degree constraints on vertices. The objective is to find a minimum cost subgraph which satisfies connectivity requirements between vertices and also degree upper bounds @math on the vertices. This includes the well-studied Minimum Bounded Degree Spanning Tree problem as a special case. Our main result is a @math -approximation algorithm for the edge-connectivity Survivable Network Design problem with degree constraints, where the cost of the returned solution is at most twice the cost of an optimum solution (satisfying the degree bounds) and the degree of each vertex @math is at most @math . This implies the first constant factor (bicriteria) approximation algorithms for many degree constrained network design problems, including the Minimum Bounded Degree Steiner Forest problem. Our results also extend to directed graphs and provide the first constant factor (bicriteria) approximation algorithms for the Minimum Bounded Degree Arborescence problem and the Minimum Bounded Degree Strongly @math -Edge-Connected Subgraph problem. In contrast, we show that the vertex-connectivity Survivable Network Design problem with degree constraints is hard to approximate, even when the cost of every edge is zero. A striking aspect of our algorithmic result is its simplicity. It is based on the iterative relaxation method, which is an extension of Jain's iterative rounding method. This provides an elegant and unifying algorithmic framework for a broad range of network design problems. We also study the problem of finding a minimum cost @math -edge-connected subgraph with at least @math vertices, which we call the @math -subgraph problem. This generalizes some well-studied classical problems such as the @math -MST and the minimum cost @math -edge-connected subgraph problems. We give a polylogarithmic approximation for the @math -subgraph problem. However, by relating it to the Densest @math -Subgraph problem, we provide evidence that the @math -subgraph problem might be hard to approximate for arbitrary @math . Given a graph @math and a subset @math of terminals, a of @math is a tree that spans @math . In the vertex-weighted Steiner tree (VST) problem, each vertex is assigned a non-negative weight, and the goal is to compute a minimum weight Steiner tree of @math . We study a natural generalization of the VST problem motivated by multi-level graph construction, the (V-GSST), which can be stated as follows: given a graph @math and terminals @math , where each terminal @math requires a facility of a minimum grade of service @math , compute a Steiner tree @math by installing facilities on a subset of vertices, such that any two vertices requiring a certain grade of service are connected by a path in @math with the minimum grade of service or better. Facilities of higher grade are more costly than facilities of lower grade. Multi-level variants such as this one can be useful in network design problems where vertices may require facilities of varying priority. While similar problems have been studied in the edge-weighted case, they have not been studied as well in the more general vertex-weighted case. We first describe a simple heuristic for the V-GSST problem whose approximation ratio depends on @math , the number of grades of service. We then generalize the greedy algorithm of [Klein & Ravi, 1995] to show that the V-GSST problem admits a @math -approximation, where @math is the set of terminals requiring some facility. This result is surprising, as it shows that the (seemingly harder) multi-grade problem can be approximated as well as the VST problem, and that the approximation ratio does not depend on the number of grades of service. Given a directed graph @math and a list @math of terminal pairs, the Directed Steiner Network problem asks for a minimum-cost subgraph of @math that contains a directed @math path for every @math . The special case Directed Steiner Tree (when we ask for paths from a root @math to terminals @math ) is known to be fixed-parameter tractable parameterized by the number of terminals, while the special case Strongly Connected Steiner Subgraph (when we ask for a path from every @math to every other @math ) is known to be W[1]-hard. We systematically explore the complexity landscape of directed Steiner problems to fully understand which other special cases are FPT or W[1]-hard. Formally, if @math is a class of directed graphs, then we look at the special case of Directed Steiner Network where the list @math of requests form a directed graph that is a member of @math . Our main result is a complete characterization of the classes @math resulting in fixed-parameter tractable special cases: we show that if every pattern in @math has the combinatorial property of being "transitively equivalent to a bounded-length caterpillar with a bounded number of extra edges," then the problem is FPT, and it is W[1]-hard for every recursively enumerable @math not having this property. This complete dichotomy unifies and generalizes the known results showing that Directed Steiner Tree is FPT [Dreyfus and Wagner, Networks 1971], @math -Root Steiner Tree is FPT for constant @math [Such 'y, WG 2016], Strongly Connected Steiner Subgraph is W[1]-hard [, SIAM J. Discrete Math. 2011], and Directed Steiner Network is solvable in polynomial-time for constant number of terminals [Feldman and Ruhl, SIAM J. Comput. 2006], and moreover reveals a large continent of tractable cases that were not known before. We study the problem of constructing universal Steiner trees for undirected graphs. Given a graph @math and a root node @math , we seek a single spanning tree @math of minimum stretch , where the stretch of @math is defined to be the maximum ratio, over all terminal sets @math , of the cost of the minimal sub-tree @math of @math that connects @math to @math to the cost of an optimal Steiner tree connecting @math to @math in @math . Universal Steiner trees (USTs) are important for data aggregation problems where computing the Steiner tree from scratch for every input instance of terminals is costly, as for example in low energy sensor network applications. We provide a polynomial time UST construction for general graphs with @math -stretch. We also give a polynomial time polylogarithmic-stretch construction for minor-free graphs. One basic building block of our algorithms is a hierarchy of graph partitions, each of which guarantees small strong diameter for each cluster and bounded neighbourhood intersections for each node. We show close connections between the problems of constructing USTs and building such graph partitions. Our construction of partition hierarchies for general graphs is based on an iterative cluster merging procedure, while the one for minor-free graphs is based on a separator theorem for such graphs and the solution to a cluster aggregation problem that may be of independent interest even for general graphs. To our knowledge, this is the first sub polynomial-stretch ( @math for any @math ) UST construction for general graphs, and the first polylogarithmic-stretch UST construction for minor-free graphs.