Zeev Nutov

TCS Journal 2026 Journal Article

A logarithmic approximation algorithm for the activation edge-multicover problem

• Zeev Nutov
• Avner Huri
• Guy Kortsarz

In the Activation Edge-Multicover problem we are given a multigraph G=(V,E) with activation costs for every edge and degree requirements for every vertex. The goal is to find an edge subset J of minimum activation cost such that every vertex has at least its required number of neighbors in the graph. Let k be the maximum requirement and theta be the maximum quotient between the two costs of an edge. For theta equal to 1 the problem admits approximation ratio O(log k). For k equal to 1 it generalizes the Set Cover problem and admits a tight approximation ratio O(log n). This implies approximation ratio O(k log n) for general k and theta, and no better approximation ratio was known. We obtain the first logarithmic approximation ratio O(log k + log min{theta,n}), bridging the two known ratios O(log k) for theta equal to 1 and O(log n) for k equal to 1. This also implies an approximation ratio for the Activation k-Connected Subgraph problem based on the best known approximation ratio for the ordinary min-cost version of the problem.

MFCS Conference 2025 Conference Paper

Tight Analysis of the Primal-Dual Method for Edge-Covering Pliable Set Families

• Zeev Nutov

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.

TCS Journal 2024 Journal Article

2-node-connectivity network design

• Zeev Nutov

We consider 2-connectivity network design problems in which we are given a graph and seek a min-size 2-connected subgraph that satisfies a prescribed property. • In the 1-Connectivity Augmentation problem the goal is to augment a connected graph by a minimum size edge subset of a specified edge set such that the augmented graph is 2-connected. We breach the natural approximation ratio 2 for this problem, and also for the more general Crossing Family Cover problem. • In the 2-Connected Dominating Set problem, we seek a minimum size 2-connected subgraph that dominates all nodes. We give the first non-trivial approximation algorithm with expected approximation ratio O ( σ ( n ) ⋅ log 3 ⁡ n ), where σ ( n ) = O ( log ⁡ n ⋅ log ⁡ log ⁡ n ⋅ ( log ⁡ log ⁡ log ⁡ n ) 3 ). The unifying technique of both results is a reduction to the Subset Steiner Connected Dominating Set problem. Such a reduction was known for edge-connectivity, and we extend it to 2-node connectivity problems. We show that the same method can be used to obtain easily polylogarithmic approximation ratios that are not too far from the best known ones for several other problems.

TCS Journal 2022 Journal Article

Approximating activation edge-cover and facility location problems

• Guy Kortsarz
• Zeev Nutov
• Eli Shalom

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 θ 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 ⊆ V of terminals, and thresholds { t u e, t v e } for each uv-edge e ∈ E. The goal is to find an assignment a = { a v: v ∈ V } to the nodes minimizing ∑ v ∈ V a v, such that the edge set E a = { e = u v: a u ≥ t u e, a v ≥ t v e } activated by a covers R. We obtain ratio 1 + max x ≥ 1 ⁡ ln ⁡ x 1 + x / θ ≈ ln ⁡ θ − ln ⁡ ln ⁡ θ for the problem, where θ ≤ max e ∈ E ⁡ max ⁡ { t u e, t v e } min ⁡ { t u e, t v e } 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 ∈ N ⁡ H k − 1 1 + k / θ, where H k = ∑ i = 1 k 1 / i. For the Min-Power Edge-Cover problem we improve the ratio 1. 406 of [4] (achieved by iterative randomized rounding) to 1. 2785. For unit thresholds we improve the ratio 73 / 60 ≈ 1. 217 of [4] to 1555 1347 ≈ 1. 155.

SODA Conference 2020 Conference Paper

A 4 + ε approximation for k -connected subgraphs

• Zeev Nutov

We obtain approximation ratio for the (undirected) k -C onnected S ubgraph problem, where is the largest integer such that 2 ℓ –1 k 2 ℓ +1 ≤ n. For large values of n this improves the ratio 6 of Cheriyan and Végh [4] when n ≥ k 3 (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.

MFCS Conference 2019 Conference Paper

Approximating Activation Edge-Cover and Facility Location Problems

• Zeev Nutov
• Guy Kortsarz
• Eli Shalom

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.

TCS Journal 2019 Journal Article

Improved approximation algorithms for minimum power covering problems

• Gruia Calinescu
• Guy Kortsarz
• Zeev Nutov

Given an undirected graph with edge costs, the power of a node is the maximum cost of an edge incident to it, and the power of a graph is the sum of the powers of its nodes. Motivated by applications in wireless networks, we consider two network design problems under the power minimization criteria. In both problems we are given a graph G = ( V, E ) with edge costs and a set T ⊆ V of terminals. The goal is to find a minimum power edge subset F ⊆ E such that the graph H = ( V, F ) satisfies some prescribed requirements. In the Min-Power Edge-Cover problem, H should contain an edge incident to every terminal. Using the Iterative Randomized Rounding (IRR) method, we give an algorithm with expected approximation ratio 1. 41; the ratio is reduced to 73 / 60 < 1. 217 when T is an independent set in G. In the case of unit costs we also achieve ratio 73/60, and in addition give a simple efficient combinatorial algorithm with ratio 5/4. For all these NP-hard problems the previous best known ratio was 3/2. In the related Min-Power Terminal Backup problem, H should contain a path from every t ∈ T to some node in T ∖ { t }. We obtain ratio 3/2 for this NP-hard problem, improving the trivial ratio of 2.

TCS Journal 2017 Journal Article

Approximating source location and star survivable network problems

• Guy Kortsarz
• Zeev Nutov

In Source Location (SL) problems the goal is to select a minimum cost source set S ⊆ V such that the connectivity (or flow) ψ ( S, v ) from S to any node v is at least the demand d v of v. In many SL problems ψ ( S, v ) = d v if v ∈ S, so the demand of nodes selected to S is completely satisfied. In a variant suggested recently by Fukunaga [7], every node v selected to S gets a “bonus” p v ≤ d v, and ψ ( S, v ) = p v + κ ( S ∖ { v }, v ) if v ∈ S and ψ ( S, v ) = κ ( S, v ) otherwise, where κ ( S, v ) is the maximum number of internally disjoint ( S, v ) -paths. While the approximability of many SL problems was seemingly settled to Θ ( ln ⁡ d ( V ) ) in [20], for his variant on undirected graphs Fukunaga achieved ratio O ( k ln ⁡ k ), where k = max v ∈ V ⁡ d v is the maximum demand. We improve this by achieving ratio min ⁡ { p ⁎ ln ⁡ k, k } ⋅ O ( ln ⁡ k ) for a more general version with node capacities, where p ⁎ = max v ∈ V ⁡ p v is the maximum bonus. In particular, for the most natural case p ⁎ = 1 we improve the ratio from O ( k ln ⁡ k ) to O ( ln 2 ⁡ k ). To derive these results, we consider a particular case of the Survivable Network (SN) problem when all edges of positive cost form a star. We obtain ratio O ( min ⁡ { ln ⁡ n, ln 2 ⁡ k } ) for this variant, improving over the best ratio known for the general case O ( k 3 ln ⁡ n ) of Chuzhoy and Khanna [4]. Finally, we obtain a logarithmic ratio for a generalization of SL where we also have edge-costs and flow-cost bounds { b v: v ∈ V }, and require that the minimum cost of a flow of value d v from S to every node v is at most b v.

TCS Journal 2013 Journal Article

A ( 1 + ln 2 ) -approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius

• Nachshon Cohen
• Zeev Nutov

We consider the Tree Augmentation problem: given a graph G = ( V, E ) with edge-costs and a tree T on V disjoint to E, find a minimum-cost edge-subset F ⊆ E such that T ∪ F is 2-edge-connected. Tree Augmentation is equivalent to the problem of finding a minimum-cost edge-cover F ⊆ E of a laminar set-family. The best known approximation ratio for Tree Augmentation is 2, even for trees of radius 2. As laminar families play an important role in network design problems, obtaining a better ratio is a major open problem in connectivity network design. We give a ( 1 + ln 2 ) -approximation algorithm for trees of constant radius. Our algorithm is based on a new decomposition of problem feasible solutions, and on an extension of Steiner Tree technique of Zelikovsky to the Set-Cover problem, which may be of independent interest.

TCS Journal 2013 Journal Article

Survivable network activation problems

• Zeev Nutov

In the Survivable Networks Activation problem we are given a graph G = ( V, E ), S ⊆ V, a family { f u v ( x u, x v ): u v ∈ E } of monotone non-decreasing activating functions from R + 2 to { 0, 1 } each, and connectivity requirements { r ( u v ): u v ∈ R } over a set R of requirement edges on V. The goal is to find a weight assignment w = { w v: v ∈ V } of minimum total weight w ( V ) = ∑ v ∈ V w v, such that in the activated graph G w = ( V, E w ), where E w = { u v: f u v ( w u, w v ) = 1 }, the following holds: for each u v ∈ R, the activated graph G w contains r ( u v ) pairwise edge-disjoint u v -paths such that no two of them have a node in S ∖ { u, v } in common. This problem was suggested recently by Panigrahi (2011) [19], generalizing the Node-Weighted Survivable Network and the Minimum-Power Survivable Network problems, as well as several other problems with motivation in wireless networks. We give new approximation algorithms for this problem. For undirected/directed graphs, our ratios are O ( k log n ) for k -Out/In-connected Subgraph Activation and k -Connected Subgraph Activation. For directed graphs this solves a question from Panigrahi (2011) [19] for k = 1, while for the min-power case and k arbitrary this solves a question from Nutov (2010) [16]. For other versions on undirected graphs, our ratios match the best known ones for the Node-Weighted Survivable Network problem (Nutov, 2009 [14]).

TCS Journal 2012 Journal Article

Approximating fault-tolerant group-Steiner problems

• Rohit Khandekar
• Guy Kortsarz
• Zeev Nutov

In this paper, we initiate the study of designing approximation algorithms for Fault-Tolerant Group-Steiner (FTGS) problems. The motivation is to protect the well-studied group-Steiner networks from edge or vertex failures. In 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 a single vertex vs. two distinct vertices from each group. The main contributions of our paper include the introduction of 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.

TCS Journal 2012 Journal Article

Improved approximation algorithms for maximum lifetime problems in wireless networks

• Zeev Nutov
• Michael Segal

A wireless ad-hoc network consists of a collection of transceivers positioned in the plane. Each transceiver is equipped with a limited battery charge. The battery charge is reduced after each transmission, depending on the transmission distance. One of the major problems in wireless network design is to route network traffic efficiently, so as to maximize the network lifetime, i. e. , the number of successful transmission rounds. In this paper, we consider Rooted Maximum Lifetime Broadcast/Convergecast problems in wireless settings. The instance consists of a directed graph G = ( V, E ) with edge-weight w ( e ) (the power needed to transmit a message along e ) for every e ∈ E, node capacity b ( v ) (the battery charge of v ) for every v ∈ V, and a root r. The goal is to find a maximum size collection { T 1, …, T k } of Broadcast/Convergecast trees rooted at r such that ∑ i = 1 k w ( δ T i ( v ) ) ≤ b ( v ), where δ T ( v ) is the set of edges leaving v in T. In the Single Topology version, the same tree is used to transmit all the messages, namely, all the Broadcast/Convergecast trees T i are identical. Using recent work on degree constrained network design problems (Nutov, 2008) [26], we give constant ratio approximation algorithms for various broadcast and convergecast problems, improving the previously best known approximation Ω ( ⌊ 1 / log n ⌋ ) by Elkin et al. (2011) [12]. Similar results are shown for the more general Rooted Maximum Lifetime Mixedcast problem, where in addition we are given an integer γ ≥ 0, and the goal is to find the maximum integer k so that k Broadcast and γ k Convergecast rounds can be performed. We also consider the model with partial level aggregation.

TCS Journal 2011 Journal Article

Approximating directed weighted-degree constrained networks

• Zeev Nutov

Given a graph H = ( V, F ) with edge weights { w e: e ∈ F }, the weighted degree of a node v in H is ∑ { w v u: v u ∈ F }. We give bicriteria approximation algorithms for problems that seek to find a minimum cost directed graph that satisfies both intersecting supermodular connectivity requirements and weighted degree constraints. The input to such problems is a directed graph G = ( V, E ) with edge-costs { c e: e ∈ E } and edge-weights { w e: e ∈ E }, an intersecting supermodular set-function f on V, and degree bounds { b ( v ): v ∈ B ⊆ V }. The goal is to find a minimum cost f -connected subgraph H = ( V, F ) (namely, at least f ( S ) edges in F enter every S ⊆ V ) of G with weighted degrees ≤ b ( v ). Our algorithm computes a solution of cost ≤ 2 ⋅ opt, so that the weighted degree of every v ∈ V is at most: 7 b ( v ) for arbitrary f and 5 b ( v ) for a 0, 1 -valued f; 2 b ( v ) + 4 for arbitrary f and 2 b ( v ) + 2 for a 0, 1 -valued f in the case of unit weights. Another algorithm computes a solution of cost ≤ 3 ⋅ opt and weighted degrees ≤ 6 b ( v ). We obtain similar results when there are both indegree and outdegree constraints, and better results when there are indegree constraints only: a ( 1, 4 b ( v ) ) -approximation algorithm for arbitrary weights and a polynomial time algorithm for unit weights. Similar results are shown for crossing supermodular f. We also consider the problem of packing maximum number k of pairwise edge-disjoint arborescences so that their union satisfies weighted degree constraints, and give an algorithm that computes a solution of value at least ⌊ k / 36 ⌋. Finally, for unit weights and without trying to bound the cost, we give an algorithm that computes a subgraph so that the degree of every v ∈ V is at most b ( v ) + 3, improving over the approximation b ( v ) + 4 of Bansal et al. (2008) [2].

TCS Journal 2011 Journal Article

Approximating some network design problems with node costs

• Guy Kortsarz
• Zeev Nutov

We study several multi-criteria undirected network design problems with node costs and lengths. All these problems are related to the Multicommodity Buy at Bulk (MBB) problem in which we are given a graph G = ( V, E ), demands { d s t: s, t ∈ V }, and a family { c v: v ∈ V } of subadditive cost functions. For every s, t ∈ V we seek to send d s t flow units from s to t, so that ∑ v c v ( f v ) is minimized, where f v is the total amount of flow through v. It is shown in Andrews and Zhang (2002) [2] that with a loss of 2 − ε in the ratio, we may assume that each s t -flow is unsplittable, namely, uses only one path. In the Multicommodity Cost–Distance (MCD) problem we are also given lengths { ℓ ( v ): v ∈ V }, and seek a subgraph H of G that minimizes c ( H ) + ∑ s, t ∈ V d s t ⋅ ℓ H ( s, t ), where ℓ H ( s, t ) is the minimum ℓ -length of an s t -path in H. The approximability of these two problems is equivalent up to a factor 2 − ε [2]. We give an O ( log 3 n ) -approximation algorithm for both problems for the case of the demands polynomial in n. The previously best known approximation ratio for these problems was O ( log 4 n ) (Chekuri et al. , 2006, 2007) [5, 6]. We also consider the Maximum Covering Tree (MaxCT) problem which is closely related to MBB: given a graph G = ( V, E ), costs { c ( v ): v ∈ V }, profits { p ( v ): v ∈ V }, and a bound C, find a subtree T of G with c ( T ) ≤ C and p ( T ) maximum. The best known approximation algorithm for MaxCT (Moss and Rabani, 2001) [18] computes a tree T with c ( T ) ≤ 2 C and p ( T ) = Ω ( opt / log n ). We provide the first nontrivial lower bound on approximation by proving that the problem admits no better than Ω ( 1 / ( log log n ) ) approximation assuming NP ⊈ Quasi(P). This holds true even if the solution is allowed to violate the budget by a constant ρ, as was done in [18] with ρ = 2. Our result disproves a conjecture of [18]. Another problem related to MBB is the Shallow Light Steiner Tree (SLST) problem, in which we are given a graph G = ( V, E ), costs { c ( v ): v ∈ V }, lengths { ℓ ( v ): v ∈ V }, a set U ⊆ V of terminals, and a bound L. The goal is to find a subtree T of G containing U with diam ℓ ( T ) ≤ L and c ( T ) minimum. We give an algorithm that computes a tree T with c ( T ) = O ( log 2 n ) ⋅ opt and diam ℓ ( T ) = O ( log n ) ⋅ L. Previously, a polylogarithmic bicriteria approximation was known only for the case of edge costs and edge lengths.

TCS Journal 2010 Journal Article

Approximating minimum power covers of intersecting families and directed edge-connectivity problems

• Zeev Nutov

Given a (directed) graph with costs on the edges, the power of a node is the maximum cost of an edge leaving it, and the power of the graph is the sum of the powers of its nodes. Let G = ( V, E ) be a graph with edge costs { c ( e ): e ∈ E } and let k be an integer. We consider problems that seek to find a min-power spanning subgraph G of G that satisfies a prescribed edge-connectivity property. In the Min-Power k -Edge-Outconnected Subgraph problem we are given a root r ∈ V, and require that G contains k pairwise edge-disjoint r v -paths for all v ∈ V − r. In the Min-Power k -Edge-Connected Subgraph problem G is required to be k -edge-connected. For k = 1, these problems are at least as hard as the Set-Cover problem and thus have an Ω ( ln | V | ) approximation threshold. For k = Ω ( n ε ), they are unlikely to admit a polylogarithmic approximation ratio [15]. We give approximation algorithms with ratio O ( k ln | V | ). Our algorithms are based on a more general O ( ln | V | ) -approximation algorithm for the problem of finding a min-power directed edge-cover of an intersecting set-family; a set-family F is intersecting if X ∩ Y, X ∪ Y ∈ F for any intersecting X, Y ∈ F, and an edge set I covers F if for every X ∈ F there is an edge in I entering X.

SODA Conference 2009 Conference Paper

An almost O (log k )-approximation for k -connected subgraphs

• Zeev Nutov

FOCS Conference 2009 Conference Paper

Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions

• Zeev Nutov

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 = max s, t¿T r(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(k 2 ) for Rooted GSN and O(k 2 log k) for Subset k-Connected Subgraph. This improves the previous ratio O(k 2 log 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(k 2 log |T|) for Rooted GSN and O(k 3 log |T|) for Subset k-Connected Subgraph, improving the ratio O(k s log 2 |T|). (3) O(k 4 log 2 |T|) for GSN; this is the first non-trivial approximation algorithm for the problem.

SODA Conference 2009 Conference Paper

Improved approximating algorithms for Directed Steiner Forest

• Moran Feldman
• Guy Kortsarz
• Zeev Nutov

TCS Journal 2009 Journal Article

Inapproximability of survivable networks

• Yuval Lando
• Zeev Nutov

In the Survivable Network Design Problem (SNDP) one seeks to find a minimum cost subgraph that satisfies prescribed node-connectivity requirements. We give a novel approximation ratio preserving reduction from Directed SNDP to Undirected SNDP. Our reduction extends and widely generalizes as well as significantly simplifies the main results of [G. Kortsarz, R. Krauthgamer, J. R. Lee, Hardness of approximation for vertex-connectivity network design problems, SIAM Journal on Computing 33 (3) (2004) 704–720]. Using it, we derive some new hardness of approximation results, as follows. We show that directed and undirected variants of SNDP and of k -Connected Subgraph are equivalent w. r. t. approximation, and that a ρ -approximation for Undirected Rooted SNDP implies a ρ -approximation for Directed Steiner Tree.

SODA Conference 2005 Conference Paper

Approximating connectivity augmentation problems

• Zeev Nutov

SODA Conference 2005 Conference Paper

Approximation algorithms for cycle packing problems

• Michael Krivelevich
• Zeev Nutov
• Raphael Yuster

STOC Conference 2004 Conference Paper

Approximation algorithm for k-node connected subgraphs via critical graphs

• Guy Kortsarz
• Zeev Nutov

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 , n /√ n - k )) for both directed and undirected graphs, and O (ln k ) for undirected graphs with n ≥ 6 k 2 , where n is the number of nodes in the input graph. Our first algorithm has approximation ratio O ( k / 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 l -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 / 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 > √ n ⁄6. Moreover, this is the first algorithm that has an 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 minimum-cost edge set to increase the outconnectivity of a directed graph by Δ a graph is said to be l -outconnected from its node r if it contains l 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 ).

MFCS Conference 2004 Conference Paper

Packing Directed Cycles Efficiently

• Zeev Nutov
• Raphael Yuster

Abstract Let G be a simple digraph. The dicycle packing number of G, denoted ν c ( G ), is the maximum size of a set of arc-disjoint directed cycles in G. Let G be a digraph with a nonnegative arc-weight function w. A function ψ from the set \({\cal C}\) of directed cycles in G to R + is a fractional dicycle packing of G if \(\sum_{e \in C \in {\cal C}} {\psi(C)} \leq w(e)\) for each e ∈ E ( G ). The fractional dicycle packing number, denoted ν \(_{c}^{\rm *}\) ( G, w ), is the maximum value of \(\sum_{C \in {\cal C}} \psi(C)\) taken over all fractional dicycle packings ψ. In case w ≡ 1 we denote the latter parameter by ν \(_{c}^{\rm *}\) ( G ). Our main result is that ν \(_{c}^{\rm *}\) ( G ) – ν c ( G )= o ( n 2 ) where n =| V ( G )|. Our proof is algorithmic and generates a set of arc-disjoint directed cycles whose size is at least ν c ( G )- o ( n 2 ) in randomized polynomial time. Since computing ν c ( G ) is an NP-Hard problem, and since almost all digraphs have ν c ( G )=Θ( n 2 ) our result is a FPTAS for computing ν c ( G ) for almost all digraphs. The latter result uses as its main lemma a much more general result. Let \({\cal F}\) be any fixed family of oriented graphs. For an oriented graph G, let \(\nu_{\cal F}(G)\) denote the maximum number of arc-disjoint copies of elements of \({\cal F}\) that can be found in G, and let \(\nu_{\cal F}^*(G)\) denote the fractional relaxation. Then, \(\nu_{\cal F}^*(G) - \nu_{\cal F}(G)=o(n^2)\). This lemma uses the recently discovered directed regularity lemma as its main tool. It is well known that ν \(_{c}^{\rm *}\) ( G, w ) can be computed in polynomial time by considering the dual problem. However, it was an open problem whether an optimal fractional dicycle packing ψyielding ν \(_{c}^{\rm *}\) ( G, w ) can be generated in polynomial time. We prove that a maximum fractional dicycle packing yielding ν \(_{c}^{\rm *}\) ( G, w ) with at most O ( n 2 ) dicycles receiving nonzero weight can be found in polynomial time.

SODA Conference 1999 Conference Paper

Approximating Multiroot 3-Outconnected Subgraphs

• Zeev Nutov

STOC Conference 1995 Conference Paper

A 2-level cactus model for the system of minimum and minimum+1 edge-cuts in a graph and its incremental maintenance

• Yefim Dinitz
• Zeev Nutov