In the k-Edge Connected Spanning Subgraph (k-ECSS) problem we are given a (multi-)graph G = (V,E) with edge costs and an integer k, and seek a min-cost k-edge-connected spanning subgraph of G. The problem admits a 2-approximation algorithm and no better approximation ratio is known. Recently, Hershkowitz, Klein, and Zenklusen [STOC 24] gave a bicriteria (1,k-10)-approximation algorithm that computes a (k-10)-edge-connected spanning subgraph of cost at most the optimal value of a standard Cut-LP for k-ECSS. We improve the bicriteria approximation to (1,k-4) and also give another non-trivial bicriteria approximation (3/2,k-2). The k-Edge-Connected Spanning Multi-subgraph (k-ECSM) problem is almost the same as k-ECSS, except that any edge can be selected multiple times at the same cost. A (1,k-p) bicriteria approximation for k-ECSS w.r.t. Cut-LP implies approximation ratio 1+p/k for k-ECSM, hence our result also improves the approximation ratio for k-ECSM.

A classic result of Williamson, Goemans, Mihail, and Vazirani [STOC 1993: 708-717] states that the problem of covering an uncrossable set family by a min-cost edge set admits approximation ratio 2, by a primal-dual algorithm with a reverse delete phase. Bansal, Cheriyan, Grout, and Ibrahimpur [ICALP 2023: 15:1–15:19] showed that this algorithm achieves approximation ratio 16 for a larger class of so called γ-pliable set families, that have much weaker uncrossing properties. The approximation ratio 16 was improved to 10 in [Z. Nutov, 2025]. Recently, Bansal [I. Bansal, 2024] obtained approximation ratio 8 for γ-pliable families and also considered an important particular case of the family of cuts of size < k of a graph H. We will improve the approximation ratio to 7 for the former case and give a simple proof of approximation ratio 6 for the latter case. Furthermore, if H is λ-edge-connected then we will show a slightly better approximation ratio 6 - 1/(β+1), where β = ⌊(k-1)/(⌈(λ+1)/2⌉)⌋. Our analysis is supplemented by examples indicating that these approximation ratios are asymptotically tight for the primal-dual algorithm.

A graph G is k-out-connected from its node s if it contains k internally disjoint sv-paths to every node v; G is k-connected if it is k-out-connected from every node. In connectivity augmentation problems, the goal is to augment a graph G₀ = (V,E₀) by a minimum costs edge set J such that G₀ ∪ J has higher connectivity than G₀. In the k-Out-Connectivity Augmentation ({k-OCA}) problem, G₀ is (k-1)-out-connected from s and G₀ ∪ J should be k-out-connected from s; in the k-Connectivity Augmentation ({k-CA}) problem G₀ is (k-1)-connected and G₀ ∪ J should be k-connected. The parameterized complexity status of these problems was open even for k = 3 and unit costs. We will show that {k-OCA} and 3-{CA} can be solved in time 9^p ⋅ n^{O(1)}, where p is the size of an optimal solution. Our paper is the first that shows fixed-parameter tractability of a k-node-connectivity augmentation problem with high values of k. We will also consider the (2,k)-Connectivity Augmentation ({(2,k)-CA}) problem where G₀ is (k-1)-edge-connected and G₀ ∪ J should be both k-edge-connected and 2-connected. We will show that this problem can be solved in time 9^p ⋅ n^{O(1)}, and for unit costs approximated within 1.892.

In this work, we study the connected version of the covering problem motivated by the coverage of ad-hoc drones’ swarm. We focus on the situation where the number of drones is given, and this number is not necessarily enough to cover all users. That is, we deal with a budget optimization problem, where the budget is the number of given drones. We assume that each ground user has different QoS requirements. Additionally, each ground user has a weight that corresponds to the importance (rank) of the user. Moreover, we consider the case when there is no third-party entity that provides connectivity to the drones. In this paper, we propose a 3D deployment scheme with the given number of drones such that the sum of the weights (ranks) of the ground users covered by drones is maximized (when the covering radii satisfy QoS of these users), and the drones form a connected graph. We present a number of approximate solutions with provable guaranteed performance evaluation that have been validated also through the simulation platform.

Let $κ(s,t)$ denote the maximum number of internally disjoint $st$-paths in an undirected graph $G$. We consider designing a compact data structure that answers $k$-bounded node connectivity queries: given $s,t \in V$ return $\min\{κ(s,t),k+1\}$. A trivial data structure has space $O(n^2)$ and query time $O(1)$. A data structure of Hsu and Lu has space $O(k^2n)$ and query time $O(\log k)$,and a randomized data structure of Iszak and Nutov has space $O(kn\log n)$ and query time $O(k \log n)$. We extend the Hsu-Lu data structure to answer queries in time $O(1)$. In parallel to our work, Pettie, Saranurak and Yin extended the Iszak-Nutov data structure to answer queries in time $O(\log n)$. Our data structure is more compact for $k<\log n$, and our query time is always better. We then augment our data structure by a list of cuts that enables to return a pointer to a minimum $st$-cut in the list (or to a cut of size $\leq k$) whenever $κ(s,t) \leq k$. A trivial data structure has cut list size $n(n-1)/2$, and cut query time $O(1)$, while the Pettie, Saranurak and Yin data structure has list size $O(kn \log n)$ and cut query time $O(\log n)$. We show that $O(kn)$ cuts suffice to return an $st$-cut of size $\leq k$, and a list of $O(k^2 n)$ cuts contains a minimum $st$-cut for every $s,t \in V$. In the case when $S$ is a node subset with $κ(s,t) \geq k$ for all $s,t \in V$, we show that $3|S|$ cuts suffice, and that these cuts can be partitioned into $O(k)$ laminar families. Thus using space $O(kn)$ we can answers each connectivity and cut queries for $s,t \in S$ in $O(1)$ time, generalizing and substantially simplifying the proof of a result of Pettie and Yin for the case $|S|=V$.

A subset S of nodes in a graph G is a k-connected m-dominating set ((k , m)-cds) if the subgraph G[S] induced by S is k-connected and every $$v \in V {\setminus } S$$ has at least m neighbors in S. In the k -Connected m -Dominating Set ((k , m)-CDS) problem, the goal is to find a minimum weight (k, m)-cds in a node-weighted graph. For $$m \ge k$$ we obtain the following approximation ratios. For unit disk graphs we improve the ratio $$O(k \ln k)$$ of Nutov (Inf Process Lett 140:30–33, 2018) to $$\min \left\{ \frac{m^2}{(m-k+1)^2},k^{2/3}\right\} \cdot O(\ln ^2 k)$$ —this is the first sublinear ratio for the problem, and the first polylogarithmic ratio $$O(\ln ^2 k)/\epsilon ^2$$ when $$m \ge (1+\epsilon )k$$ ; furthermore, we obtain ratio $$\min \left\{ \frac{m}{m-k+1},\sqrt{k}\right\} \cdot O(\ln ^2 k)$$ for uniform weights. For general graphs our ratio $$O(k \ln n)$$ improves the previous best ratio $$O(k^2 \ln n)$$ of Nutov (2018) and matches the best known ratio for unit weights of Zhang et al. (INFORMS J Comput 30(2):217–224, 2018). These results are obtained by showing the same ratios for the Subset k -Connectivity problem when the set of terminals is an m-dominating set.

We obtain approximation ratio for the (undirected) k-Connected Subgraph problem, where is the largest integer such that 2ℓ–1k2ℓ+1 ≤ n. For large values of n this improves the ratio 6 of Cheriyan and Végh [4] when n ≥ k3 (the case ℓ = 1). Our result implies an fpt-approximation ratio 4 + ε that matches (up to the “+ε” term) the best known ratio 4 for k = 6, 7 for both the general and the easier augmentation versions of the problem. Similar results are shown for the problem of covering an arbitrary crossing supermodular biset function.

What approximation ratio can we achieve for the Facility Location problem if whenever a client u connects to a facility v, the opening cost of v is at most theta times the service cost of u? We show that this and many other problems are a particular case of the Activation Edge-Cover problem. Here we are given a multigraph G=(V,E), a set R subseteq V of terminals, and thresholds {t^e_u,t^e_v} for each uv-edge e in E. The goal is to find an assignment a={a_v:v in V} to the nodes minimizing sum_{v in V} a_v, such that the edge set E_a={e=uv: a_u >= t^e_u, a_v >= t^e_v} activated by a covers R. We obtain ratio 1+max_{x>=1}(ln x)/(1+x/theta)~= ln theta - ln ln theta for the problem, where theta is a problem parameter. This result is based on a simple generic algorithm for the problem of minimizing a sum of a decreasing and a sub-additive set functions, which is of independent interest. As an application, we get the same ratio for the above variant of {Facility Location}. If for each facility all service costs are identical then we show a better ratio 1+max_{k in N}(H_k-1)/(1+k/theta), where H_k=sum_{i=1}^k 1/i. For the Min-Power Edge-Cover problem we improve the ratio 1.406 of [Calinescu et al, 2019] (achieved by iterative randomized rounding) to 1.2785. For unit thresholds we improve the ratio 73/60~=1.217 of [Calinescu et al, 2019] to 1555/1347~=1.155.

There are two errors in our article “Approximating Minimum-Cost Connectivity Problems via Uncrossable Bifamilies” ( ACM Transactions on Algorithms ( TALG ), 9(1), Article No. 1, 2012). In that article, we consider the (undirected) S URVIVABLE N ETWORK problem. The input consists of a graph G =( V , E ) with edge-costs, a set T ⊆ V of terminals, and connectivity demands { r st > 0 : st ∈ D ⊆ T × T } . The goal is to find a minimum cost subgraph of G that for all st ∈ D contains r st pairwise internally disjoint st -paths. We claimed ratios O ( k ln k ) for rooted demands when the set D of demand pairs form a star, where k = max st ∈ D r st is the maximum demand. This ratio is correct when the requirements are r st = k for all t ∈ T \{ s }, but for general rooted demands our article implies only ratio O ( k 2 ) (which, however, is still the currently best-known ratio for the problem). We also obtained various ratios for the node-weighted version of the problem. These results are valid, but the proof needs a correction described here.

In the Tree Augmentation problem we are given a tree T=(V,F) and a set E of edges with positive integer costs {c_e:e in E}. The goal is to augment T by a minimum cost edge set J subseteq E such that T cup J is 2-edge-connected. We obtain the following results. Recently, Adjiashvili [SODA 17] introduced a novel LP for the problem and used it to break the 2-approximation barrier for instances when the maximum cost M of an edge in E is bounded by a constant; his algorithm computes a 1.96418+epsilon approximate solution in time n^{{(M/epsilon^2)}^{O(1)}}. Using a simpler LP, we achieve ratio 12/7+epsilon in time ^{O(M/epsilon^2)}. This also gives ratio better than 2 for logarithmic costs, and not only for constant costs. In addition, we will show that (for arbitrary costs) the problem admits ratio 3/2 for trees of diameter <= 7. One of the oldest open questions for the problem is whether for unit costs (when M=1) the standard LP-relaxation, so called Cut-LP, has integrality gap less than 2. We resolve this open question by proving that for unit costs the integrality gap of the Cut-LP is at most 28/15=2-2/15. In addition, we will suggest another natural LP-relaxation that is much simpler than the ones in previous work, and prove that it has integrality gap at most 7/4.

In the Steiner k -Forest problem, we are given an edge weighted graph, a collection D of node pairs, and an integer k ⩽ | D |. The goal is to find a min-weight subgraph that connects at least k pairs. The best known ratio for this problem is min { O (√ n ), O (√ k )} [Gupta et al. 2010]. In Gupta et al. [2010], it is also shown that ratio ρ for Steiner k -Forest implies ratio O (ρ · log 2 n ) for the related Dial-a-Ride problem. The only other algorithm known for Dial-a-Ride, besides the one resulting from Gupta et al. [2010], has ratio O (√ n ) [Charikar and Raghavachari 1998]. We obtain approximation ratio n 0.448 for Steiner k -Forest and Dial-a-Ride with unit weights, breaking the O (√ n ) approximation barrier for this natural case. We also show that if the maximum edge-weight is O ( n ϵ ), then one can achieve ratio O ( n (1 + ϵ) · 0.448 ), which is less than √ n if ϵ is small enough. The improvement for Dial-a-Ride is the first progress for this problem in 15 years. To prove our main result, we consider the following generalization of the Minimum k -Edge Subgraph (M k -ES) problem, which we call Min-Cost ℓ-Edge-Profit Subgraph (MCℓ-EPS): Given a graph G = ( V , E ) with edge-profits p = { p e : e ∈ E } and node-costs c = { c v : v ∈ V }, and a lower profit bound ℓ, find a minimum node-cost subgraph of G of edge-profit at least ℓ. The M k -ES problem is a special case of MCℓ-EPS with unit node costs and unit edge profits. The currently best known ratio for M k -ES is n 3-2√2 + ϵ [Chlamtac et al. 2012]. We extend this ratio to MCℓ-EPS for general node costs and profits bounded by a polynomial in n , which may be of independent interest.

In the Tree Augmentation Problem (TAP) the goal is to augment a tree T by a minimum size edge set F from a given edge set E such that T+F is 2-edge-connected. The best approximation ratio known for TAP is 1.5. In the more general Weighted TAP problem, F should be of minimum weight. Weighted TAP admits several 2-approximation algorithms w.r.t. the standard cut-LP relaxation. The problem is equivalent to the problem of covering a laminar set family. Laminar set families play an important role in the design of approximation algorithms for connectivity network design problems. In fact, Weighted TAP is the simplest connectivity network design problem for which a ratio better than 2 is not known. Improving this "natural" ratio is a major open problem, which may have implications on many other network design problems. It seems that achieving this goal requires finding an LP-relaxation with integrality gap better than 2, which is an old open problem even for TAP. In this paper we introduce two different LP-relaxations, and for each of them give a simple algorithm that computes a feasible solution for TAP of size at most 7/4 times the optimal LP value. This gives some hope to break the ratio 2 for the weighted case.

The Tree Augmentation Problem (TAP) is as follows: given a connected graph G =( V , ε ) and an edge set E on V , find a minimum size subset of edges F ⊆ E such that ( V , ε ∪ F ) is 2-edge-connected. In the conference version [Even et al. 2001] was sketched a 1.5-approximation algorithm for the problem. Since a full proof was very complex and long, the journal version was cut into two parts. The first part [Even et al. 2009] only proved ratio 1.8. An attempt to simplify the second part produced an error in Even et al. [2011]. Here we give a correct, different, and self-contained proof of the ratio 1.5 that is also substantially simpler and shorter than the previous proofs.

We consider the problem of finding a minimum edge cost subgraph of a graph satisfying both given node-connectivity requirements and degree upper bounds on nodes. We present an iterative rounding algorithm of the biset linear programming relaxation for this problem. For directed graphs and $k$-out-connectivity requirements from a root, our algorithm computes a solution that is a 2-approximation on the cost, and the degree of each node $v$ in the solution is at most $2b(v) + O(k)$, where $b(v)$ is the degree upper bound on $v$. For undirected graphs and element-connectivity requirements with maximum connectivity requirement $k$, our algorithm computes a solution that is a $4$-approximation on the cost, and the degree of each node $v$ in the solution is at most $4b(v)+O(k)$. These ratios improve the previous $O(\log k)$-approximation on the cost and $O(2^k b(v))$-approximation on the degrees. Our algorithms can be used to improve approximation ratios for other node-connectivity problems such as undirected $k$-out-connectivity, directed and undirected $k$-connectivity, and undirected rooted $k$-connectivity and subset $k$-connectivity.

In the Steiner k-Forest problem we are given an edge weighted graph, a collection D of node pairs, and an integer k \leq |D|. The goal is to find a minimum cost subgraph that connects at least k pairs. The best known ratio for this problem is min{O(sqrt{n}),O(sqrt{k})} [Gupta et al., 2008]. In [Gupta et al., 2008] it is also shown that ratio rho for Steiner k-Forest implies ratio O(rho log^2 n) for the Dial-a-Ride problem: given an edge weighted graph and a set of items with a source and a destination each, find a minimum length tour to move each object from its source to destination, but carrying at most k objects at a time. The only other algorithm known for Dial-a-Ride, besides the one resulting from [Gupta et al., 2008], has ratio O(sqrt{n}) [Charikar and Raghavachari, 1998]. We obtain ratio n^{0.448} for Steiner k-Forest and Dial-a-Ride with unit weights, breaking the O(sqrt{n}) ratio barrier for this natural special case. We also show that if the maximum weight of an edge is O(n^{epsilon}), then one can achieve ratio O(n^{(1+epsilon) 0.448}), which is less than sqrt{n} if epsilon is small enough. To prove our main result we consider the following generalization of the Minimum k-Edge Subgraph (Mk-ES) problem, which we call Min-Cost l-Edge-Profit Subgraph (MCl-EPS): Given a graph G=(V,E) with edge-profits p={p_e: e in E} and node-costs c={c_v: v in V}, and a lower profit bound l, find a minimum node-cost subgraph of G of edge profit at least l. The Mk-ES problem is a special case of MCl-EPS with unit node costs and unit edge profits. The currently best known ratio for Mk-ES is n^{3-2*sqrt{2} + epsilon} (note that 3-2*sqrt{2} < 0.1716). We extend this ratio to MCl-EPS for arbitrary node weights and edge profits that are polynomial in n, which may be of independent interest.

We consider connectivity problems with orientation constraints. Given a directed graph $D$ and a collection of ordered node pairs $P$ let $P[D]=\{(u,v) \in P: D \mbox{ contains a } uv\mbox{-path}\}$. In the \sf Steiner Forest Orientation problem we are given an undirected graph $G=(V,E)$ with edge-costs and a set $P \subseteq V \times V$ of ordered node pairs. The goal is to find a minimum-cost subgraph $H$ of $G$ and an orientation $D$ of $H$ such that $P[D]=P$. We give a $4$-approximation algorithm for this problem. In the \sf Maximum Pairs Orientation problem we are given a graph $G$ and a multicollection of ordered node pairs $P$ on $V$. The goal is to find an orientation $D$ of $G$ such that $|P[D]|$ is maximum. Generalizing the result of Arkin and Hassin [Discrete Appl. Math., 116 (2002), pp. 271--278] for $|P|=2$, we will show that for a mixed graph $G$ (that may have both directed and undirected edges), one can decide in $n^{O(|P|)}$ time whether $G$ has an orientation $D$ with $P[D]=P$. (For undirected graphs this problem admits a polynomial time algorithm for any $P$, but it is NP-complete on mixed graphs.) For undirected graphs, we will show that one can decide whether $G$ admits an orientation $D$ with $|P[D]| \geq k$ in $O(n+m)+2^{O(k\cdot \log \log k)}$ time; hence this decision problem is fixed-parameter tractable, which answers an open question from Dorn et al. [Algorithms Molecular Biol., 6 (2011)]. We also show that \sf Maximum Pairs Orientation admits ratio $O(\log |P|/\log\log |P|)$, which is better than the ratio $O(\log n/\log\log n)$ of Gamzu, Segev, and Sharan [Proceedings of WABI 2010, pp. 215--225] when $|P|

Abstract Given a graph H = (U, E) and connectivity requirements r = {r(u,v) : u, v ∈ R ⊆ U}, we say that H satisfies r if it contains r(u, v) pairwise internally‐disjoint uv‐paths for all u, v ∈ R. We consider the Survivable Network with Minimum Number of Steiner Points (SN‐MSP) problem: given a finite set V of points in a normed space (M, ‖·‖) and connectivity requirements, find a minimum size set S ⊂ M \ V of additional points, such that the unit disc graph induced by U = V ∪ S satisfies the requirements. In the (node‐connectivity) Survivable Network Design Problem (SNDP) we are given a graph G = (V, E) with edge costs and connectivity requirements, and seek a minimum cost subgraph H of G that satisfies the requirements. Let k = maxu,v ∈ Vr(u, v) denote the maximum connectivity requirement. We will show a natural transformation of an SN‐MSP instance (V, r) into an SNDP instance (G = (V, E), c, r), such that an α‐approximation algorithm for the SNDP instance implies an α · O(k2)‐approximation algorithm for the SN‐MSP instance. In particular, for the case of uniform requirements r(u, v) = k for all u, v ∈ V, we obtain for SN‐MSP the ratio O(k2 ln k), which solves an open problem from (Bredin et al. Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc) (2005), 309–319). © 2012 Wiley Periodicals, Inc. NETWORKS, 2012

In the Steiner Network problem, we are given a graph G with edge-costs and connectivity requirements r uv between node pairs u,v . The goal is to find a minimum-cost subgraph H of G that contains r uv edge-disjoint paths for all u,v ∈ V . In Prize-Collecting Steiner Network problems, we do not need to satisfy all requirements, but are given a penalty function for violating the connectivity requirements, and the goal is to find a subgraph H that minimizes the cost plus the penalty. The case when r uv ∈ {0,1} is the classic Prize-Collecting Steiner Forest problem. In this article, we present a novel linear programming relaxation for the Prize-Collecting Steiner Network problem, and by rounding it, obtain the first constant-factor approximation algorithm for submodular and monotone nondecreasing penalty functions. In particular, our setting includes all-or-nothing penalty functions, which charge the penalty even if the connectivity requirement is slightly violated; this resolves an open question posed by Nagarajan et al. [2008]. We further generalize our results for element-connectivity and node-connectivity.

We give approximation algorithms for the Survivable Network problem. The input consists of a graph G = ( V,E ) with edge/node-costs, a node subset S ⊆ V , and connectivity requirements { r ( s,t ): s,t ∈ T ⊆ V }. The goal is to find a minimum cost subgraph H of G that for all s,t ∈ T contains r ( s,t ) pairwise edge-disjoint st -paths such that no two of them have a node in S ∖ { s,t } in common. Three extensively studied particular cases are: Edge-Connectivity Survivable Network ( S = ∅), Node-Connectivity Survivable Network ( S = V ), and Element-Connectivity Survivable Network ( r ( s,t ) = 0 whenever s ∈ S or t ∈ S ). Let k = max s,t ∈ T r ( s,t ). In Rooted Survivable Network, there is s ∈ T such that r ( u,t ) = 0 for all u ≠ s , and in the Subset k -Connected Subgraph problem r ( s,t ) = k for all s,t ∈ T . For edge-costs, our ratios are O ( k log k ) for Rooted Survivable Network and O ( k 2 log k ) for Subset k -Connected Subgraph. This improves the previous ratio O ( k 2 log n ), and for constant values of k settles the approximability of these problems to a constant. For node-costs, our ratios are as follows. — O ( k log | T |) for Element-Connectivity Survivable Network, matching the best known ratio for Edge-Connectivity Survivable Network. — O ( k 2 log | T |) for Rooted Survivable Network and O ( k 3 log | T |) for Subset k -Connected Subgraph, improving the ratio O ( k 8 log 2 | T |). — O ( k 4 log 2 | T |) for Survivable Network; this is the first nontrivial approximation algorithm for the node-costs version of the problem.

The (undirected) Steiner Network problem is as follows: given a graph $G=(V,E)$ with edge/node-weights and edge-connectivity requirements $\{r(u,v):u,v\in U\subseteq V\}$, find a minimum-weight subgraph H of G containing U so that the $uv$-edge-connectivity in H is at least $r(u,v)$ for all $u,v\in U$. The seminal paper of Jain [Combinatorica, 21 (2001), pp. 39–60], and numerous papers preceding it, considered the Edge-Weighted Steiner Network problem, with weights on the edges only, and developed novel tools for approximating minimum-weight edge-covers of several types of set functions and families. However, for the Node-Weighted Steiner Network ( NWSN ) problem, nontrivial approximation algorithms were known only for $0,1$ requirements. We make an attempt to change this situation by giving the first nontrivial approximation algorithm for NWSN with arbitrary requirements. Our approximation ratio for NWSN is $r_{\max}\cdot O(\ln|U|)$, where $r_{\max}=\max_{u,v\in U}r(u,v)$. This generalizes the result of Klein and Ravi [J. Algorithms, 19 (1995), pp. 104–115] for the case $r_{\max}=1$. We also give an $O(\ln|U|)$-approximation algorithm for the node-connectivity variant of NWSN (when the paths are required to be internally disjoint) for the case $r_{\max}=2$. Our results are based on a much more general approximation algorithm for the problem of finding a minimum node-weighted edge-cover of an uncrossable set-family. Finally, we give evidence that a polylogarithmic approximation ratio for NWSN with large $r_{\max}$ might not exist even for $|U|=2$ and unit weights.

We study approximation algorithms, integrality gaps, and hardness of approximation of two problems related to cycles of “small” length k in a given (undirected) graph. The instance for these problems consists of a graph $G=(V,E)$ and an integer k. The k-Cycle Transversal problem is to find a minimum edge subset of E that intersects every k-cycle. The k-Cycle-Free Subgraph problem is to find a maximum edge subset of E without k-cycles. Our main result is for the k-Cycle-Free Subgraph problem with even values of k. For any $k=2r$, we give an $\Omega(n^{-\frac{1}{r}+\frac{1}{r(2r-1)}-\varepsilon})$-approximation scheme with running time $(1/\varepsilon)^{O(1/\varepsilon)}\mathsf{poly}(n)$, where $n=|V|$ is the number of vertices in the graph. This improves upon the ratio $\Omega(n^{-1/r})$ that can be deduced from extremal graph theory. In particular, for $k=4$ the improvement is from $\Omega(n^{-1/2})$ to $\Omega(n^{-1/3-\varepsilon})$. Our additional result is for odd k. The 3-Cycle Transversal problem (covering all triangles) was studied by Krivelevich [Discrete Math., 142 (1995), pp. 281–286], who presented an LP-based 2-approximation algorithm. We show that k-Cycle Transversal admits a $(k-1)$-approximation algorithm, which extends to any odd k the result that Krivelevich proved for $k=3$. Based on this, for odd k we give an algorithm for k-Cycle-Free Subgraph with ratio $\frac{k-1}{2k-3}=\frac{1}{2}+\frac{1}{4k-6}$; this improves upon the trivial ratio of $1/2$. For $k=3$, the integrality gap of the underlying LP was posed as an open problem in the work of Krivelevich. We resolve this problem by showing a sequence of graphs with integrality gap approaching 2. In addition, we show that if k-Cycle Transversal admits a $(2-\varepsilon)$-approximation algorithm, then so does the Vertex-Cover problem; thus improving the ratio 2 is unlikely. Similar results are shown for the problem of covering cycles of length $\leq k$ or finding a maximum subgraph without cycles of length $\leq k$ (i.e., with girth $>k$).

We give approximation algorithms for the Generalized Steiner Network (GSN) problem. The input consists of a graph G = (V, E) with edge/node costs, a node subset S ¿ V, and connectivity requirements {r(s, t) : s,t ¿ T ¿ V}. The goal is to find a minimum cost subgraph H that for all s, t ¿ T contains r(s, t) pairwise edge-disjoint si-paths so that no two of them have a node in S - {s, t} in common. Three extensively studied particular cases are: Edge-GSN (S = 0), Node-GSN (S = V), and Element-GSN (r(s,t) = 0 whenever s ¿ S or t ¿ S). Let k = maxs,t¿Tr(s, t). In Rooted GSN there is s ¿ T so that r(u, t) = 0 for all u¿s, and in the Subset k-Connected Subgraph problem r(s, t) = k for all s, t ¿ T. For edge costs, our ratios are: O(k2) for Rooted GSN and O(k2log k) for Subset k-Connected Subgraph. This improves the previous ratio O(k2log n) and settles the approximability of these problems to a constant for bounded k. For node-cost, our ratios are: (1) O(k log |T|) for Element-GSN, matching the best known ratio for Edge-GSN. (2) O(k2log |T|) for Rooted GSN and O(k3log |T|) for Subset k-Connected Subgraph, improving the ratio O(kslog2|T|). (3) O(k4log2|T|) for GSN; this is the first non-trivial approximation algorithm for the problem.

In this paper, we initiate the study of designing approximation algorithms for {\sf Fault-Tolerant Group-Steiner} ({\sf FTGS}) problems. The motivation is to protect the well-studied group-Steiner networks from edge or vertex failures. In {\sf Fault-Tolerant Group-Steiner} problems, we are given a graph with edge- (or vertex-) costs, a root vertex, and a collection of subsets of vertices called groups. The objective is to find a minimum-cost subgraph that has two edge- (or vertex-) disjoint paths from each group to the root. We present approximation algorithms and hardness results for several variants of this basic problem, e.g., edge-costs vs. vertex-costs, edge-connectivity vs. vertex-connectivity, and $2$-connecting from each group a single vertex vs. many vertices. Main contributions of our paper include the introduction of very general structural lemmas on connectivity and a charging scheme that may find more applications in the future. Our algorithmic results are supplemented by inapproximability results, which are tight in some cases. Our algorithms employ a variety of techniques. For the edge-connectivity variant, we use a primal-dual based algorithm for covering an {\em uncros\-sable} set-family, while for the vertex-connectivity version, we prove a new graph-theoretic lemma that shows equivalence between obtaining two vertex-disjoint paths from two vertices and $2$-connecting a carefully chosen single vertex. To handle large group-sizes, we use a $p$-Steiner tree algorithm to identify the ``correct'' pair of terminals from each group to be connected to the root. We also use a non-trivial charging scheme to improve the approximation ratio for the most general problem we consider.

We consider the k-Directed Steiner Forest (k-DSF) problem: given a directed graph G = (V, E) with edge costs, a collection D ⊆ V × V of ordered node pairs, and an integer k ≤ |D|, find a min-cost subgraph H of G that contains an st-path for (at least) k pairs (s, t) ∊ D. When k = |D|, we get the Directed Steiner Forest (DSF) problem. The best known approximation ratios for these problems are: for k-DSF by Charikar et al. [2], and O(k1/2+∊) for DSF by Chekuri et al. [3]. For DSF we give an O(n∊.min{n4/5, m2/3})-approximation scheme using a novel LP-relaxation seeking to connect pairs via “cheap” paths. This is the first sub-linear (in terms of n = |V|) approximation ratio for the problem. For k-DSF we give a simple greedy O(k1/2+∊)-approximation scheme, improving the best known ratio by Charikar et al. [2], and (almost) matching, in terms of k, the best ratio known for the undirected variant [11]. Even when used for the particular case DSF, our algorithm favorably compares to the one of [3], which repeatedly solves linear programs, and uses complex time and space consuming transformations.

We consider two cases of the Survivable Network Design (SND) problem: given a complete graph Gn = (V, En) with costs on the edges and connectivity requirements {r(u, v):u,v ∊ V}, find a minimum cost subgraph G of Gn that contains r(u, v) internally disjoint uv-paths for all u, v ∊ V. Our main result is an -approximation algorithm for the k-Connected Subgraph problem (the case r(u, v) = k for all u, v ∊ V), for both directed and undirected graphs, where n = |V|. Our ratio is O(log k), unless k = n – o(n). Previously, the best known approximation guarantees for this problem were O(log2 k) for directed/undirected graphs [Kortsarz and Nutov STOC 2004, Fakcharoenphol and Laekhanukit STOC 2008], and O(log k) for undirected graphs with [Cheriyan, Vempala, and Vetta STOC 2002]. As in previous work, we consider the k-Connectivity Augmentation problem of increasing at minimum cost the connectivity of a given graph J from k − 1 to k; a ρ-approximation for it is used to derive an O(ρ · log k)-approximation for k-Connected Subgraph. Fakcharoenphol and Laekhanukit showed that k-Connectivity Augmentation admits an O(log v)-approximation algorithm, where v is the number of minimal “violated” sets in J. However, we may have v = Θ(n), so this gives only an O(log n)-approximation. We design a novel primal-dual algorithm that adds an edge set of cost ≤ opt to get . Combined with the algorithm of Fakcharoenphol and Laekhanukit, this gives the ratio for k-Connectivity Augmentation, which is O(1), unless k = n – o(n). Our additional result is for the (undirected) Rooted SND, where for a “root” s ∊ V, the connectivity requirements are {r(s, t) = r(t): t ∊ T ⊆ V}, and the solution graph should contain r(t) internally disjoint st-paths for all t ∊ T. For large values of k = maxt ∊ T r(t) Rooted SND is at least as hard to approximate as Directed Steiner Tree [Lando and Nutov APPROX 2008]. For Rooted SND [Chakraborty, Chuzhoy, Khanna STOC 08] gave recently a kO(k2) log4 n-approximation algorithm. Slightly later [Chuzhoy and Khanna FOCS 08] improved the ratio to O(k2 log n), and also gave an O(k8 log2 n)-approximation algorithm for the case of node-costs. Independently, we obtained a simple approximation algorithm with ratios O(k2 log n) for edge-costs, and O(k4 log2 n) for node-costs.

We present a 1.8-approximation algorithm for the following NP-hard problem: Given a connected graph G = ( V , E ) and an edge set E on V disjoint to E , find a minimum-size subset of edges F ⊆ E such that ( V , E ∪ F ) is 2-edge-connected. Our result improves and significantly simplifies the approximation algorithm with ratio 1.875 + ε of Nagamochi.

Let G = ( V , E ) be an undirected graph and let S ⊆ V . The S-connectivity λ S G ( u , v ) of a node pair ( u , v ) in G is the maximum number of uv -paths that no two of them have an edge or a node in S - { u , v } in common. The corresponding Connectivity Augmentation (CA) problem is: given a graph G = ( V , E ), a node subset S ⊆ V , and a nonnegative integer requirement function r ( u , v ) on V × V , add a minimum size set F of new edges to G so that λ S G + F ( u , v ) ≥ r ( u , v ) for all ( u , v ) ∈ V × V . Three extensively studied particular cases are: the Edge-CA ( S = ∅), the Node-CA ( S = V ), and the Element-CA ( r ( u , v )= 0 whenever u ∈ S or v ∈ S ). A polynomial-time algorithm for Edge-CA was developed by Frank. In this article we consider the Element-CA and the Node-CA, that are NP-hard even for r ( u , v ) ∈ {0,2}. The best known ratios for these problems were: 2 for Element-CA and O ( r max ṡ ln n ) for Node-CA, where r max = max u , v ∈ V r ( u , v ) and n = | V |. Our main result is a 7/4-approximation algorithm for the Element-CA, improving the previously best known 2-approximation. For Element-CA with r ( u , v ) ∈ {0,1,2} we give a 3/2-approximation algorithm. These approximation ratios are based on a new splitting-off theorem, which implies an improved lower bound on the number of edges needed to cover a skew-supermodular set function. For Node-CA we establish the following approximation threshold: Node-CA with r ( u , v ) ∈ {0, k } cannot be approximated within O (2 log 1-ϵ n ) for any fixed ϵ > 0, unless NP ⊆ DTIME( n polylog( n ) ).

The cycle packing number ν e ( G ) of a graph G is the maximum number of pairwise edge-disjoint cycles in G . Computing ν e ( G ) is an NP-hard problem. We present approximation algorithms for computing ν e ( G ) in both undirected and directed graphs. In the undirected case we analyze a variant of the modified greedy algorithm suggested by Caprara et al. [2003] and show that it has approximation ratio Θ(√log n ), where n = | V ( G )|. This improves upon the previous O (log n ) upper bound for the approximation ratio of this algorithm. In the directed case we present a √ n -approximation algorithm. Finally, we give an O ( n 2/3 )-approximation algorithm for the problem of finding a maximum number of edge-disjoint cycles that intersect a specified subset S of vertices. We also study generalizations of these problems. Our approximation ratios are the currently best-known ones and, in addition, provide upper bounds on the integrality gap of standard LP-relaxations of these problems. In addition, we give lower bounds for the integrality gap and approximability of ν e ( G ) in directed graphs. Specifically, we prove a lower bound of Ω(log n /loglog n ) for the integrality gap of edge-disjoint cycle packing. We also show that it is quasi-NP-hard to approximate ν e ( G ) within a factor of O (log 1 − ε n ) for any constant ε > 0. This improves upon the previously known APX-hardness result for this problem.

Abstract The Directed Multicut (DM) problem is: given a simple directed graph G = ( V , E ) with positive capacities u e on the edges, and a set K ⊆ V × V of ordered pairs of nodes of G , find a minimum capacity K ‐multicut; C ⊆ E is a K ‐multicut if in G − C there is no ( s , t )‐path for any ( s , t ) ⫅ K . In the uncapacitated case (UDM) the goal is to find a minimum size K ‐multicut. The best approximation ratio known for DM is $O(\min\{\sqrt{n},opt\})$ by Gupta, where n = | V |, and opt is the optimal solution value. All known nontrivial approximation algorithms for the problem solve large linear programs. We give the first combinatorial approximation algorithms for the problem. Our main result is an Õ ( n 2/3 / opt 1/3 )‐approximation algorithm for UDM, which improves the $O(\min\{opt,\sqrt{n}\})$ ‐approximation for opt = Ω( n 1/2+ϵ ). Combined with the article of Gupta, we get that UDM can be approximated within better than $O(\sqrt n)$ , unless $opt={\tilde \Theta}(\sqrt n)$ . We also give a simple and fast O ( n 2/3 )‐approximation algorithm for DM. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(4), 214–217 2005

We present two new approximation algorithms for the problem of finding a k-node connected spanning subgraph (directed or undirected) of minimum cost. The best known approximation guarantees for this problem were $O(\min \{k,\frac{n}{\sqrt{n-k}}\})$ for both directed and undirected graphs, and $O(\ln k)$ for undirected graphs with $n \geq 6k^2$, where n is the number of nodes in the input graph. Our first algorithm has approximation ratio $O(\frac{n}{n-k}\ln^2 k)$, which is $O(\ln^2 k)$ except for very large values of k, namely, $k=n-o(n)$. This algorithm is based on a new result on $\ell$-connected p-critical graphs, which is of independent interest in the context of graph theory. Our second algorithm uses the primal-dual method and has approximation ratio $O(\sqrt{n} \ln k)$ for all values of $n,k$. Combining these two gives an algorithm with approximation ratio $O(\ln k \cdot \min \{\sqrt{k},\frac{n}{n-k} \ln k\})$, which asymptotically improves the best known approximation guarantee for directed graphs for all values of $n,k$, and for undirected graphs for $k>\sqrt{n/6}$. Moreover, this is the first algorithm that has an approximation guarantee better than $\Theta(k)$ for all values of $n,k$. Our approximation ratio also provides an upper bound on the integrality gap of the standard LP-relaxation.

We present two new approximation algorithms for the problem of finding a k-node connected spanning subgraph (directed or undirected) of minimum cost. The best known ap-n proximation guarantees for this problem were O(min{k, for both directed and undirected graphs, and O(ln k) for undirected graphs with n ≥ 6k 2, where n is the number of nodes in the input graph. Our first algorithm has approximation ratio O ( k n−k ln2 k), which is O(ln 2 k) except for very large values of k, namely, k = n − o(n). This algorithm is based on a new result on ℓ-connected p-critical graphs, which is of independent interest in the context of graph theory. Our second algorithm uses the primal-dual method and has approximation ratio O ( √ n ln k) for all values of n, k. Combining these two gives an algorithm with approximation ratio O(ln k · min { √ k k, ln k}), which asymptotically im-n−k proves the best known approximation guarantee for directed graphs for all values of n, k, and for undirected graphs for k> n/6. Moreover, this is the first algorithm that has an n−k approximation guarantee better than Θ(k) for all values of n, k. Our approximation ratio also provides an upper bound on the integrality gap of the standard LP-relaxation to the problem. As a byproduct, we also get the following result which is of independent interest. To get a faster implementation of our algorithms, we consider the problem of adding a minimumcost edge set to increase the outconnectivity of a directed graph by ∆; a graph is said to be ℓ-outconnected from its node r if it contains ℓ internally disjoint paths from r to any other node. The best known time complexity for the later problem is O(m 3). For the particular case of ∆ = 1, we give a primal-dual algorithm with running time O(m 2). Categories and Subject Descriptors

Consider the following problem: Given an undirected graph with nonnegative edge costs and requirements ku for every node u, find a minimum-cost subgraph that contains max{ku, kv} internally disjoint paths between every pair of nodes u, v. For k = max ku ≥ 2, this problem is NP-hard. The best-known algorithm for it has an approximation ratio of 2(k − 1). For a general instance of the problem, for no value of k ≥ 2, a better approximation algorithm was known. We consider the case of small requirements ku ∈ {1, 2, 3}; these may arise in applications, as, in practical networks, the connectivity requirements are usually rather small. For this case, we give an algorithm with an approximation ratio of . This improves the best previously known approximation ratio of 4. Our algorithm also implies an improvement for arbitrary k. In the case in which we have an initial graph which is 2-connected, our algorithm achieves an approximation ratio of 2. © 2000 John Wiley & Sons, Inc.

Article A 2-level cactus model for the system of minimum and minimum+1 edge-cuts in a graph and its incremental maintenance Share on Authors: Yefim Dinitz Dept. of Computer Science, Technion, Haifa, Israel Dept. of Computer Science, Technion, Haifa, IsraelView Profile , Zeev Nutov Dept. of Applied Mathematics, Technion, Haifa, Israel Dept. of Applied Mathematics, Technion, Haifa, IsraelView Profile Authors Info & Claims STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computingMay 1995 Pages 509–518https://doi.org/10.1145/225058.225268Online:29 May 1995Publication History 11citation328DownloadsMetricsTotal Citations11Total Downloads328Last 12 Months18Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access