Abstract 1 Introduction 2 The Capacitated Graph 3 The Links Graph 4 The rank of the incidence matrix of small cuts and links 5 The Capacitated Graph: Deferred Proofs References

A Bad Example for Jain’s Iterative Rounding Theorem for the Cover Small Cuts Problem

Miles Simmons ORCID Department of Combinatorics and Optimization, University of Waterloo, Canada    Ishan Bansal ORCID Amazon, Bellevue, WA, USA    Joe Cheriyan ORCID Department of Combinatorics and Optimization, University of Waterloo, Canada
Abstract

The Cover⁢Small⁢Cuts problem is a key problem in Network Design. In the Cover⁢Small⁢Cuts problem, we are given a capacitated (undirected) graph G=(V,E,u) and a threshold value λ, as well as a set of links L with end-nodes in V and a non-negative cost for each link ℓ∈L; the goal is to find a minimum-cost set of links such that each non-trivial cut of capacity less than λ is covered by a link.

Jain’s iterative rounding theorem is a well-known result in the area of approximation algorithms and, more broadly, in combinatorial optimization. The theorem asserts that LP relaxations of several problems in network design and combinatorial optimization have the following key property: for every basic feasible solution x there exists a variable xe that has value at least a constant (e.g., xe≥12).

We construct an example showing that this property fails to hold for the standard LP relaxation of the Cover⁢Small⁢Cuts problem. This indicates that the polyhedron of feasible solutions to the LP (for Cover⁢Small⁢Cuts) differs in an essential way from the polyhedrons associated with several problems in combinatorial optimization. Moreover, our example shows that a direct application of Jain’s iterative rounding algorithm does not give an O⁢(1) approximation algorithm for Cover⁢Small⁢Cuts.

We mention that Bansal et al. [6] showed that the WGMV primal-dual algorithm, due to Williamson et al. [19], applied to the same standard LP relaxation achieves approximation ratio 16 for the Cover⁢Small⁢Cuts problem. That is, the WGMV primal-dual algorithm, applied to the same LP relaxation, finds an integer solution of cost ≤16 times the optimal value of the LP.

Keywords and phrases:
approximation algorithms, capacitated network design, covering small cuts, edge-connectivity of graphs, f-connectivity problem, iterative rounding method, primal-dual method
Category:
APPROX
Funding:
Ishan Bansal: This work is external and does not relate to the position at Amazon.
Joe Cheriyan: Supported in part by NSERC grant RGPIN-2024-04473.
Copyright and License:
[Uncaptioned image] © Miles Simmons, Ishan Bansal, and Joe Cheriyan; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation → Approximation algorithms analysis
Related Version:
Previous Version: https://doi.org/10.48550/arXiv.2504.13105
Acknowledgements:
We thank the anonymous reviewers and the Approx 2026 PC for their comments. We are grateful to Sharat Ibrahimpur for reading a preliminary version, and for valuable comments.
Editors:
Mohit Singh and Tom Gur

1 Introduction

The Cover⁢Small⁢Cuts problem has emerged as a key problem in Network Design since the publication of the first major result in ICALP 2023, see [5, 6]. In the Cover⁢Small⁢Cuts problem, we are given a capacitated (undirected) graph G=(V,E,u) and a threshold value λ, as well as a set of links L with end-nodes in V and a non-negative cost cℓ for each link ℓ∈L; the goal is to find a minimum-cost set of links such that each non-trivial cut of capacity less than λ is covered by a link. In more detail, a subset F⊆L of links is said to cover a node-set S if there exists a link ℓ∈F with exactly one end-node in S, and the objective is to find a minimum-cost F⊆L that covers each nonempty S⊊V such that u⁢(δE⁢(S))<λ. Bansal et al. [6] formulated this problem, and they showed that the WGMV primal-dual algorithm, due to Williamson et al. [19], achieves approximation ratio 16 for this problem. Later, Bansal [2, 3] and Nutov [15] proved that the same algorithm achieves approximation ratio 6. Simmons et al. [18, 17] improved the approximation ratio to 5. Recently, Nutov [16] constructed an example of the Cover⁢Small⁢Cuts problem such that the WGMV primal-dual algorithm finds a solution of cost (5−ϵ)⁢opt, where opt denotes the cost of an optimal (integral) solution and ϵ>0 is an arbitrarily small number. This shows that the 5-approximation analysis of [18, 17] is tight We mention that the same problem is called by other names in the recent literature, e.g., AugSmallCuts [6], Small Cut Augmentation [3], Small Cuts Cover [15], etc.

We may use abbreviations for some standard terms, e.g., we may use Cover⁢Small⁢Cuts as an abbreviation for “the Cover⁢Small⁢Cuts problem”.

Given a graph G=(V,E) whose edges have both costs and capacities, a fundamental task in network design is to find a spanning subgraph of minimum cost that satisfies some specified edge-connectivity requirements. Capacitated network design refers to the more general (and more challenging) setting where edges have non-uniform capacities. This topic has attracted intense research efforts over the last few years; see below for discussion and citations. In the context of algorithmic research and combinatorial optimization, the Cap-k-ECSS problem sits in the core of capacitated network design. In this problem, we are given an (undirected) graph G=(V,E), where each edge has a non-negative cost and a positive integer capacity, and the algorithmic goal is to find a minimum-cost spanning subgraph such that every non-trivial cut has capacity k or more. Let n=|V| and let um⁢i⁢n (respectively, um⁢a⁢x) denote the minimum (respectively, maximum) capacity of an edge; assume that um⁢a⁢x≤k. One of the earliest approximation algorithms for Cap-k-ECSS is due to Goemans et al. [10], and it achieves an approximation ratio of min⁡{2⁢k,|E|}. Over the last three decades, there have been several advances, and the best approximation ratio known is min⁡(O⁢(log⁡n),O⁢(log⁡(k/um⁢i⁢n)),k,2⁢um⁢a⁢x), due to, respectively, Chakrabarty et al. [8], Bansal et al. [4], and Boyd et al. [7]. Let us mention that there are no known hardness results that rule out the possibility of better asymptotic approximation ratios. Most of the advances of this decade on Cap-k-ECSS are based on O⁢(1) approximation algorithms for Cover⁢Small⁢Cuts.

For the benefit of readers who are not familiar with the papers cited above, let us sketch a simple reduction from Cap-k-ECSS to Cover⁢Small⁢Cuts that incurs a multiplicative factor of ⌈kum⁢i⁢n⌉ in the approximation ratio, see [6, section 5] for further details, and see section 1.3 below for our notation. The algorithm is as follows: Initialize the “solution” edge-set F to be the empty set; during the execution of the algorithm, GF=(V,F) is our current “solution graph.” While the minimum capacity of a cut δF⁢(S),∅≠S⊊V, in (V,F) is less than k, run an α-approximation algorithm for Cover⁢Small⁢Cuts with input GF=(V,F) and with link-set L:=E−F, to augment all cuts δF⁢(S),∅≠S⊊V, with u⁢(δF⁢(S))<k and obtain a valid augmentation F′⊆L. Update F by adding F′, that is, F:=F∪F′. On exiting the while loop, output the edge-set F. Bansal et al. [6, Theorem 1.3] show that the cost of F is ≤α⋅⌈kum⁢i⁢n⌉⋅opt, where opt denotes the optimal cost for the Cap-k-ECSS instance.

1.1 Jain’s iterative rounding method and the 𝒇-connectivity problem

Jain’s iterative rounding method [12] and its extensions such as iterative relaxation [14] form a key theoretical tool for proving approximation guarantees, as well as characterizing optimal solutions of well-known (poly-time solvable) problems in combinatorial optimization.

Several connectivity augmentation problems can be formulated in a general framework called f-connectivity. In this problem, we are given an undirected graph G=(V,E) on n nodes with nonnegative costs c∈ℚ≥0E on the edges and a requirement function f:2V→ℤ≥0 on subsets of nodes. The algorithmic goal is to find an edge-set J⊆E with minimum cost c⁢(J):=∑e∈Jce such that for all cuts δ⁢(S),S⊆V, we have |δ⁢(S)∩J|≥f⁢(S). A function f is called weakly supermodular if f⁢(V)=0, and for all A,B⊆V, either f⁢(A)+f⁢(B)≤f⁢(A−B)+f⁢(B−A), or f⁢(A)+f⁢(B)≤f⁢(A∩B)+f⁢(A∪B). The following is an LP relaxation for the f-connectivity problem.

min ∑e∈Ece⁢xe (LP: f-connectivity)
subject to: ∑e∈E∩δ⁢(S)xe≥f⁢(S) ∀S⊂V
0≤xe≤1 ∀e∈E.

Assuming that the function f is weakly supermodular, integral, and has a positive value for some S⊂V, Jain [12] presented a 2-approximation algorithm for the f-connectivity problem, based on the following key result.

Theorem 1 (Jain [12, Theorem 3.1]).

Assume that the function f is weakly supermodular, integral, non-negative and non-zero. Then, in any basic feasible solution x to the LP relaxation, for at least one edge, e, xe is at least 1/2.

The Jain property

For the sake of notational convenience, let us define a particular LP relaxation of a combinatorial problem to have the Jain property if there exists a constant c0 such that every basic feasible solution x of the LP relaxation has an entry xe such that xe≥1/c0 (i.e., the infinity norm of x is lower-bounded by a constant).

1.2 Our main result: A bad extreme point for the LP relaxation of 𝐂𝐨𝐯𝐞𝐫⁢𝐒𝐦𝐚𝐥𝐥⁢𝐂𝐮𝐭𝐬

We construct an example showing that the Jain property fails to hold for the standard LP relaxation of the Cover⁢Small⁢Cuts problem, and we mention that the WGMV primal-dual algorithm applied to the same LP relaxation finds an integer solution of cost ≤6⋅LPopt. This indicates that the polyhedron of feasible solutions to the LP relaxation (for Cover⁢Small⁢Cuts) differs in an essential way from the polyhedrons associated with several problems in combinatorial optimization. Moreover, our example shows that a direct application of Jain’s iterative rounding algorithm does not give an O⁢(1) approximation algorithm for Cover⁢Small⁢Cuts.

Consider an instance G=(V,E,u),λ of the Cover⁢Small⁢Cuts problem. Let 𝒞={∅≠S⊊V:u⁢(δE⁢(S))<λ}. Then we have the following covering LP relaxation of the problem.

LPopt:=min ∑f∈Lcf⁢xf (LP: Cover Small Cuts)
subject to: ∑f∈L∩δ⁢(S)xf≥1 ∀S∈𝒞
0≤xf ∀f∈L.
▶ Remark 2.

Let fCSC:2V→{0,1} be the requirement function for Cover⁢Small⁢Cuts; thus, for S⊆V, fCSC⁢(S)=1 iff S∈𝒞. Although fCSC is not weakly supermodular, fCSC is a pliable function that satisfies property (γ), see [6] for definitions, and the O⁢(1) approximation analysis of [6] relies on this.

Theorem 3.

Let k≥4 be an even integer. There is an instance of the Cover⁢Small⁢Cuts problem G=(V,E),L,u such that the LP relaxation (LP: Cover Small Cuts) has a basic feasible solution x∗ such that every positive variable of x∗ has value 1/k.

Discussion and contrast with previous results

Jain’s iterative rounding theorem [12] (see Theorem 1 above) asserts that for the LP relaxation of f-connectivity, whenever f is weakly supermodular, every basic feasible solution x has at least one variable xe≥12. This Jain property is the lever behind Jain’s 2-approximation algorithm and has been applied widely in network design; see [14] for a comprehensive treatment. A natural question is whether the Jain property extends beyond the weakly supermodular setting, in particular, to LP relaxations of problems with node-connectivity requirements. The short answer is no, and the previous literature shows that there are (at least) two distinct reasons.

The first, and fundamental, reason comes from the area of hardness of approximation. Kortsarz, Krauthgamer, and Lee [13] proved that the node-connectivity Survivable Network Design Problem (NC-SNDP) admits no polynomial-time O⁢(1)-approximation algorithm unless NP⊆DTIME⁢(nO⁢(log⁡log⁡n)). Since the natural LP relaxation of NC-SNDP can be solved in polynomial time via a separation oracle based on max-flow computations, this hardness result implies – by a direct contrapositive argument – that the Jain property cannot hold for that LP: if every basic feasible solution x had some variable xe≥1/c0 for a fixed positive constant c0, then iterating Jain’s rounding scheme would yield a polynomial-time O⁢(1)-approximation algorithm, contradicting the hardness result of [13].

The second reason is constructive: one can show directly that the standard LP relaxations for certain node-connectivity problems do not have the Jain property; nevertheless, it is possible that the underlying problem may admit a good approximation algorithm via a different LP relaxation or method. Fleischer, Jain, and Williamson [9] studied iterative rounding for minimum-cost node-connectivity problems and showed that it gives a 2-approximation for the element connectivity problem – a relaxation of node connectivity in which two “source-sink” paths are permitted to share so-called terminal nodes (but are required to be disjoint on the edges and the Steiner nodes). Their analysis establishes that the Jain property holds for the standard LP relaxation of element connectivity. Crucially, however, their result does not extend to the node-connectivity setting: the requirement function for node connectivity is not weakly supermodular, and the LP does not inherit the Jain property. For the mincost k-node-connected spanning subgraph problem (mincost k-NCSS), which is the core problem of node-connectivity network design, Aazami, Cheriyan, and Laekhanukit [1] gave an explicit family of bad examples for the standard iterative rounding method. Specifically, they constructed instances for which the setpair LP relaxation has a basic feasible solution x satisfying maxe⁡xe≤O⁢(1)/k, thereby showing that the standard iterative rounding method cannot achieve an approximation ratio better than Ω⁢(k) for mincost k-NCSS.

Our main result, Theorem 3, differs from the previous results in two essential ways.

(a) Edge-connectivity versus node-connectivity.

The results of [13, 9, 1] all concern problems with node-connectivity requirements: the requirement function counts internally node-disjoint paths (or a relaxation thereof). Our bad example, by contrast, applies to the Cover⁢Small⁢Cuts problem, which has edge-connectivity requirements; recall that the goal is to find a minimum-cost set of links such that every cut of edge-capacity less than λ is covered by at least one link. The standard LP relaxation of Cover⁢Small⁢Cuts (see (LP: Cover Small Cuts)) is a covering LP of the same type as the LP for f-connectivity, yet our construction shows that the Jain property does not hold for it. To the best of our knowledge, there is no prior bad example for the Jain property for any problem defined by uniform edge-connectivity requirements.

(b) Hardness versus polyhedral structure.

A key distinction between our result and the hardness-based argument of [13] is that Cover⁢Small⁢Cuts does admit a polynomial-time O⁢(1)-approximation algorithm [6, 3, 15], achieved via the primal-dual method of Williamson et al. [19], rather than iterative rounding. Thus the failure of the Jain property for Cover⁢Small⁢Cuts cannot be attributed to hardness of approximation. This separates Cover⁢Small⁢Cuts from NC-SNDP: for NC-SNDP, the Jain property fails (in part) because the problem is hard to approximate; for Cover⁢Small⁢Cuts, the problem allows an O⁢(1) approximation algorithm, but the known iterative rounding methods via the natural covering LP cannot achieve an O⁢(1) approximation ratio. In the context of network design on undirected graphs with uniform edge-connectivity requirements, our construction indicates that the “limits” of the iterative rounding method are “tighter” than what is indicated by the previous literature.

1.3 Basic notation and definitions

For a positive integer k, we use [k] to denote the set {1,2,…,k}. A pair of subsets A,B of V (the ground-set) is said to cross if each of the four sets A∩B,V−(A∪B),A−B,B−A is nonempty.

For a graph G=(V,E) and S⊆V, the cut δE⁢(S) refers to the set of edges that have exactly one end-node in S; δE⁢(S) is called a non-trivial cut if ∅≠S⊊V.

For each of the minimization problems (in network design or flexible graph connectivity), we use opt to denote the optimal value (i.e., the minimum cost of an integer solution), and LPopt to denote the optimal value of an LP relaxation. The context will resolve potential ambiguities.

2 The Capacitated Graph

Let k≥4 be an even integer. The capacitated graph G=(V,E),u has n=2+(k2) nodes, and m=(n−1)+(k−1)=(k2)+k edges. The edge capacities are chosen from the set {1,2,3} and λ (the threshold value for small cuts) is chosen to be 5.

We denote the nodes of G by v1,v2,…,vn, as well as by the indices 1,2,…,n. For notational convenience, let s=v1 and let t=vn.

The family of small cuts consists of two sub-families. One sub-family corresponds to the node-sets N1={v1},N2={v1,v2},…,Nn−1={v1,v2,…,vn−1}. In other words, for each of the sets Ni={v1,v2,…,vi},i=1,…,n−1, δE⁢(Ni) is a small cut. We call the sets Ni (i=1,…,n−1) the nested sets. The other sub-family corresponds to the (k−1) node-sets Q1={v2,v3,…,v1+k2},Q2={v2+k2,v3+k2,…,v1+2⋅k2},…,Q(k−1)={v2+(k−2)⋅k2,v3+(k−2)⋅k2,…,v1+(k−1)⋅k2}. Note that these sets form a partition of V⁢(G)−{s,t} into (k−1) sets, each of cardinality k/2. In other words, for each of the (k−1) “intervals” Qj (j=1,…,k−1) formed by picking the node with index 2+(j−1)⋅k2 and the next (k2−1) consecutively indexed nodes, δE⁢(Qj) is a small cut. We call the sets Qj (j=1,…,k−1) the Q-sets; moreover, by the first node of Qj we mean the node of lowest index in Qj (i.e., node 2+(j−1)⋅k2), and by the last node of Qj we mean the node of highest index in Qj (i.e., node 1+(j)⋅k2). For notational convenience, let Q0={s}={v1} and let Qk={t}={vn}; moreover, let s=v1 be the last node of Q0 and let t=vn be the first node of Qk. (Consequently, in the proofs below, s may only serve as the last node of a Q-set, and t may only serve as a first node. Thus, if we examine the case that a specified node v is a first node, it is guaranteed that v≠s (i.e., the Q-set containing v is not Q0); similarly, if we examine the case that a specified node v is a last node, it is guaranteed that v≠t (i.e., the Q-set containing v is not Qk)).

For a nested set Ni (i=1,…,n−1) and a Q-set Qj (j=1,…,k−1), observe that s=v1∈Ni−Qj and t=vn∉Ni∪Qj; moreover, if Ni∩Qj is nonempty, then either Qj crosses Ni (i.e., both Qj−Ni and Qj∩Ni are nonempty) or Qj⊊Ni.

There are two types of edges in G. There are n−1 edges that form the s,t-path v1,v2,…,vn; we use E1 to denote the edge set of this path. The first edge and the last edge of this path have capacity 2, thus, uv1⁢v2=2=uvn−1⁢vn. Consider any other edge vi⁢vi+1 (i=2,…,n−2) of this path. If both vi and vi+1 are in the same Q-set then vi⁢vi+1 has capacity 3, otherwise, vi⁢vi+1 has capacity one. Moreover, there are (k−1) other edges (that are not in the s,t-path), and each of these edges has capacity one; we use E2 to denote this set of (k−1) edges. The nodes incident to the j-th edge of E2 (j=1,…,k−1) have indices 1+(j−1)⋅k2 and 2+j⋅k2. Thus, E2 has an edge between s=v1 and the first node of Q2, an edge between the last node of Qk−2 and t=vn, and, for each j=1,…,k−3, E2 has an edge between the last node of Qj and the first node of Qj+2.

The following figure illustrates the construction of the capacitated graph for k=4; the graph has (k2)+2=8 nodes and (k2)+k=10 edges.

Figure 1: The capacitated graph for k=4. The small cuts are given by the nested sets N1,…,N7 (indicated by dashed lines) and the sets Q1,Q2,Q3 (indicated by ovals).

We defer the proofs of the next two results to section 5; our proofs are straightforward and use case analysis.

Proposition 4.

Each of the nested cuts δ⁢(Ni),i=1,…,n−1 and each of the Q-cuts δ⁢(Qj),j=1,…,k−1 has capacity less than λ=5.

Proposition 5.

Every non-trivial cut δ⁢(S), ∅⊊S⊊V, of G that is neither a nested cut nor a Q-cut has capacity ≥λ=5.

3 The Links Graph

Let (V,L) denote the graph of the links; thus L is the set of links, and we denote the links by the symbol ℓ, e.g., ℓi, ℓ′, etc. The number of links is m=n+k−2=(k2)+k. The links are partitioned into k internally node disjoint s,t-paths that we denote by P1,…,Pk−1,Pk. The s,t-path Pk has one link s⁢t=v1⁢vn. Each of the s,t-paths P1,…,Pk−1 has k/2 internal nodes and has 1+k2 links. Moreover, the sequence of node indices of each of these s,t-paths is an increasing sequence; that is, the node sequence has the form v1,vi2,vi3,…,vi(k2+1),vn, where 1<i2<i3<⋯<i(k2+1)<n. Each of the nodes v2,…,vn−1 is in one of the s,t-paths P1,…,Pk−1; thus, each of these nodes is incident to two links.

Recall that we have (k−1) Q-sets, each with k/2 nodes, and (k−1) s,t-paths P1,…,Pk−1 each with k/2 internal nodes. Each of the s,t-paths Pi (i=1,…,k−1) is constructed such that it is incident to precisely one node of k/2 (of the (k−1)) Q-sets, and it is disjoint from the other (k−1−k2) Q-sets. The s,t-path Pi (i=1,…,k−1) is incident to the Q-set with index i and the next (k/2)−1 consecutively indexed Q-sets (with “wrap around”); thus, for i=1,…,k−1 and j=1,…,k−1, the s,t-path Pi and the set Qj have a node in common iff

j≥i andj≤min⁡(i+k2−1,k−1),or
j<i and1≤j≤i−k2.

If an s,t-path Pi and a set Qj have a node in common, then any one node of Qj could be assigned to Pi; in other words, our construction does not specify the internal nodes of Pi, it only specifies the Q-sets that intersect Pi.

Let AP⁢Q denote the (k−1)×(k−1) zero-one matrix that has a row for each s,t-path Pi (i=1,…,k−1) and a column for each set Qj (i=1,…,k−1) such that the entry Ai,jP⁢Q is one iff Pi and Qj have a node in common. Then, by construction, AP⁢Q is a circulant matrix with entries of zero or one such that each row has k/2 consecutive ones (with “wrap around”) and the remaining (k−1−k2) entries of the row are zero. Observe that the number of ones in each row, k/2, and the size of the matrix, k−1, are relatively prime (i.e., gcd⁡(k2,k−1)=1). For an illustration, see the example at the end of section 4.

Lemma 6.

The matrix AP⁢Q has rank (k−1). Moreover, det(AP⁢Q)=k/2.

One can prove this lemma directly, by applying row operations (and applying the matrix determinant lemma 111https://en.wikipedia.org/wiki/Matrix_determinant_lemma to a square matrix with diagonal entries 2 and all other entries one). Alternatively, the lemma follows directly from a result of Hariprasad [11, Theorem 2.1].

Figure 2 illustrates the construction of the links graph for k=4. The graph has (k2)+2=8 nodes and (k2)+k=10 links. The links partition into k=4 (internally node disjoint) s,t-paths P1,…,P4; the links of P1,…,P4 are indicated by distinct colours.

Figure 2: The links graph for k=4. The links partition into s,t-paths P1,…,P4, and the links of each of these s,t-paths is indicated by a distinct colour. Thus, the links of P1 are ℓ1,ℓ5,ℓ7, the links of P2 are ℓ2,ℓ8,ℓ9, the links of P3 are ℓ3,ℓ6,ℓ10, and P4 has the link ℓ4. The small cuts are given by the nested sets N1,…,N7 (indicated by dashed lines) and the sets Q1,Q2,Q3 (indicated by ovals).

We construct a basic feasible solution x∗ by assigning the value 1/k to each link, thus, xℓ∗=1/k,∀ℓ∈L. Informally speaking, we are assigning a value 1/k to each of the s,t-paths P1,…,Pk. It is easy to verify that each of the small cuts, namely, δ⁢(Ni) (i=1,…,n−1) and δ⁢(Qj) (j=1,…,k−1), is “tightly covered” by x∗. First, consider a cut δ⁢(Ni) (i=1,…,n−1), and observe that each of the s,t-paths P1,…,Pk has exactly one of its links in δ⁢(Ni), hence, x∗⁢(δ⁢(Ni))=(k)⁢1k=1. Next, consider a cut δ⁢(Qj) (j=1,…,k−1), and observe that k/2 of the s,t-paths P1,…,Pk have exactly one internal node in Qj, hence, each of these s,t-paths has exactly two links in δ⁢(Qj), therefore, x∗⁢(δ⁢(Qj))=2⁢(k2)⁢(1k)=1. Note that the tight constraints at x∗ are the covering constraints for the small cuts, and none of the lower bound constraints is tight (since 0<1/k<1).

The basis matrix A of x∗ has one row for each small cut and one column for each link; the entry of A corresponding to a small cut δ⁢(S) and a link ℓ is one if ℓ∈δ⁢(S), otherwise, the entry is zero. Thus, A is an m×m matrix with entries of zero or one; recall that m=n+k−2=(k2)+k. In the next section, we show that matrix A has full rank, and that will prove our claim that x∗ is a basic feasible solution of the LP relaxation of Cover⁢Small⁢Cuts.

4 The rank of the incidence matrix of small cuts and links

Let A denote the zero-one incidence matrix of the small cuts and the links; A is an m×m matrix, where m=n+k−2=(k2)+k. The matrix A has rows corresponding to the cuts of the Q-sets followed by rows corresponding to the cuts of the nested sets; the columns of A correspond to the links. In this section, the main goal is to show that det(A) is non-zero; equivalently, A has full rank. We start by fixing a convenient indexing for the rows and columns of A. The rows 1,…,(k−1) of A correspond to the cuts of Q1,…,Q(k−1), and the rows k,(k+1),…,m of A correspond to the cuts of N1,…,N(n−1). The links ℓ∈L are indexed as follows: The link of the s,t-path Pi (i=1,…,k) incident to node s=v1 is denoted ℓi; thus, each of ℓ1,…,ℓk is in δ⁢(s), and there is a bijection between these links and the s,t-path P1,…,Pk. Note that each of the remaining links is incident to one of the nodes v2,…,vn−1, and, for each i=2,…,(n−1), the unique link that is incident to node vi and is in the cut δ⁢(Ni) is assigned the index (k+i−1). The columns 1,…,m of A correspond to the links ℓ1,…,ℓm.

Let us view the matrix A as a 2×2 block matrix (A11A12A21A22) where A11 is the (k−1)×(k−1) sub-matrix of A whose rows correspond to the cuts of Q1,…,Q(k−1) and whose columns correspond to the links ℓ1,…,ℓ(k−1), and A22 is the (m−k+1)×(m−k+1) sub-matrix of A whose rows correspond to the cuts of N1,…,N(n−1) and whose columns correspond to the links ℓk,ℓ(k+1),…,ℓm.

Claim 7.

The sub-matrix A22 is lower-triangular and all entries on the diagonal are one; thus, det(A22)=1.

Proof.

The link ℓk (with end nodes s and t) is in each of the cuts δ⁢(Ni), i=1,…,(n−1). For each of the links ℓ(k+i−1) where i=2,…,(n−1), note that the link is in the cut δ⁢(Ni) and it is in none of the cuts δ⁢(N1),…,δ⁢(N(i−1)). ⊲

Our plan is to apply row operations to the first (k−1) rows of A in order to transform the submatrix (A11A12) to a submatrix of the form ((AP⁢Q)⊤0(k−1)×(m−k+1)), where (AP⁢Q)⊤ denotes the transpose of the matrix AP⁢Q and 0(k−1)×(m−k+1) denotes a (k−1)×(m−k+1) matrix of zeros. Therefore, using row operations, we will rewrite the matrix A as the 2×2 block matrix ((AP⁢Q)⊤0(k−1)×(m−k+1)A21A22); then, by applying Lemma 6 as well as a result on the determinant of 2×2 block matrices, we see that the determinant of the re-written matrix A is det(AP⁢Q)⁢det(A22)=det(AP⁢Q)≠0.

See the example at the end of this section for an illustration.

Let us introduce some notation to describe and analyse our row operations. For any set of links L′ let χL′ denote the zero-one row incidence vector of L′; thus, for any link ℓ, χℓL′=1 iff ℓ∈L′. Note that rows 1,…,(k−1) of A correspond to χδ⁢(Q1),…,χδ⁢(Q(k−1)). For any link ℓ, let ϕ⁢(ℓ) denote the index i of the s,t-path Pi that contains ℓ. For each of the links ℓi, i=1,…,(k−1), note that ϕ⁢(ℓi)=i, since we have a bijection between these links and the s,t-paths P1,…,P(k−1). For any set of links L′, let Φ⁢(L′) denote the set of indices of the s,t-paths P1,…,P(k−1) that contain at least one of the links of L′; thus, Φ⁢(L′)⊆{1,…,k}, and index i is in Φ⁢(L′) iff the s,t-path Pi contains one of the links of L′. For example, if L′ is a subset of {ℓ1,…,ℓ(k−1)}, then Φ⁢(L′)={i:ℓi∈L′}.

Consider any row j, j=1,…,(k−1) of the matrix A; this row-vector is the same as χδ⁢(Qj). Let g denote the largest index i such that the nested set Ni is disjoint from Qj, and let h denote the smallest index i such that the nested set Ni contains Qj. (By our construction, the k/2 nodes of Qj are in the interval [(g+1),(g+2),…,h].)

Claim 8.

(χδ⁢(Qj)−χδ⁢(Nh)+χδ⁢(Ng))= 2⁢χL′, where L′ is the set of k/2 links in δ⁢(Qj)∩δ⁢(Ng).

Proof.

By construction, every link has its two end nodes in two different Q-sets. Hence, every link ℓ∈δ⁢(Qj) that has its lower-index node in Qj is in δ⁢(Nh); similarly, every link ℓ∈δ⁢(Qj) that has its higher-index node in Qj is in δ⁢(Ng). Moreover, δ⁢(Ng)−δ⁢(Qj)=δ⁢(Nh)−δ⁢(Qj) is the set of links that have their lower-index node in Ng and their higher-index node in V−Nh. The equation in the claim follows from these statements. ⊲

In the above claim, note that L′ is contained in the cut of a Q-set, hence, the link ℓk=s⁢t cannot be in L′.

Our plan is to (separately) apply the row operations described in the above claim to each of the rows j=1,…,(k−1) of A. The next lemma explains how to apply row operations to χL′, where L′ is any set of k/2 links contained in some nested cut δ⁢(Ni) and ℓk∉L′, to transform χL′ to the vector χL^, where L^={ℓi:i∈Φ⁢(L′)}. Informally speaking, we can apply row operations to “map” any row vector χL′, where L′⊂δ⁢(Ni)−{ℓk} and |L′|=k/2, to the row incidence vector (padded with zeros on the right) of the k/2 s,t-paths among P1,…,P(k−1) that contain (at least) one of the links of L′. Thus, by applying the above claim and the next lemma, we “map” each row of the submatrix (A11A12) to a distinct row of the submatrix ((AP⁢Q)⊤0(k−1)×(m−k+1)).

Lemma 9.

Let i=1,…,n−1, and let L′⊂δ⁢(Ni)−{ℓk} be any set of k/2 links. By applying row operations, one can transform the vector χL′ to the vector χL^, where L^={ℓi:i∈Φ⁢(L′)}.

Proof.

By induction on the index of the nested set whose cut contains L′.

Let h be the smallest index such that the nested cut δ⁢(Nh) contains L′. If h=1, then we have L^=L′ and the lemma is proved.

Now, suppose h≥2; thus, L′ contains a link ℓj with j>k. Observe that L′ contains the link ℓ(h+k−1) which is incident to node vh and is in the cut δ⁢(Nh); informally speaking, the presence of ℓ(h+k−1) in L′ certifies that L′ is contained in δ⁢(Nh) and L′ is not a subset of δ⁢(Nj) for any j<h. Let L¯ denote the set of links δ⁢(Nh)−L′; L¯ is a “complementary set” of k/2 links w.r.t. δ⁢(Nh) and L′. For every link ℓj∈L¯, observe that j<(h+k−1) (since ℓj∈δ⁢(Nh) and ℓ(h+k−1)∉L¯).

Let g be the smallest index such that the nested cut δ⁢(Ng) contains L¯. Again, observe that L¯ contains the link ℓ(g+k−1) which is incident to node vg and is in the cut δ⁢(Ng). Clearly, g<h and δ⁢(Ng)≠δ⁢(Nh), since ℓ(h+k−1)∈δ⁢(Nh) and ℓ(h+k−1)∉δ⁢(Ng).

Claim 10.

There exists a set of k/2 links of δ⁢(Ng)−{ℓk}, call it L′′, such that

  1. (i)

    χL′′=χL′−χδ⁢(Nh)+χδ⁢(Ng), and

  2. (ii)

    Φ⁢(L′′)=Φ⁢(L′).

Proof.

Observe that L¯=δ⁢(Nh)−L′, and that L¯ is contained in δ⁢(Ng); also, note that ℓk is in L¯. Let L′′=δ⁢(Ng)−L¯; observe that L′′ is a set of k/2 links and ℓk∉L′′. Hence, we have χδ⁢(Ng)−χδ⁢(Nh)=χL′′−χL′. This proves part (i) of the claim.

Moreover, note that each of the nested cuts contains exactly one link from each of the s,t-paths P1,…,Pk; that is, for each i=1,…,n−1, Φ⁢(δ⁢(Ni))={1,…,k}. Hence, Φ⁢(L′)=Φ⁢(δ⁢(Nh)−L¯)={1,…,k}−Φ⁢(L¯)=Φ⁢(δ⁢(Ng)−L¯)=Φ⁢(L′′). This proves part (ii) of the claim. ⊲

In the induction step (of the proof of the lemma), we apply the above claim to replace the set L′ by the set L′′; note that L′′ has the properties of L′ (listed in the lemma statement) and Φ⁢(L′′)=Φ⁢(L′). Moreover, L′′ is contained in the cut of a nested set of smaller index than the index of any nested set whose cut contains L′.

Thus, the lemma follows by induction. ◀

Our main result of this section follows from the above discussion.

Theorem 3. [Restated, see original statement.]

Let k≥4 be an even integer. There is an instance of the Cover⁢Small⁢Cuts problem G=(V,E),L,u such that the LP relaxation (LP: Cover Small Cuts) has a basic feasible solution x∗ such that every positive variable of x∗ has value 1/k.

4.1 Example with 𝒌=𝟒

In this subsection, we fix k=4, and we illustrate our row operations, in particular, the row operations of Claims 8,10, on the links graph shown in Figure 2. The links partition into s,t-paths P1,…,P4, and the links of P1 are ℓ1,ℓ5,ℓ7, the links of P2 are ℓ2,ℓ8,ℓ9, the links of P3 are ℓ3,ℓ6,ℓ10, and P4 has the link ℓ4.

The incidence matrix AP⁢Q of the s,t-paths P1,P2,P3 and the Q-sets is given below.

The incidence matrix A of the small cuts and the links is given below. Note that the submatrix A22 (of the nested cuts and the links ℓ4,…,ℓ10) is lower-triangular with diagonal entries of one.

We describe the row operations for δ⁢(Q1),δ⁢(Q2),δ⁢(Q3), i.e., rows 1,2,3 of A; in particular, we describe the row operations of Claims 8,10.

Q1:

χδ⁢(Q1)=χ{ℓ1,ℓ3,ℓ5,ℓ6}. In Claim 8, for j=1, we have h=3,g=1. (χδ⁢(Q1)−χδ⁢(N3)+χδ⁢(N1))= 2⁢χ{ℓ1,ℓ3}.

Note that Φ⁢(δ⁢(Q1))={1,3}.

Q2:

χδ⁢(Q2)=χ{ℓ2,ℓ5,ℓ7,ℓ8}. In Claim 8, for j=2, we have h=5,g=3. (χδ⁢(Q2)−χδ⁢(N5)+χδ⁢(N3))= 2⁢χ{ℓ2,ℓ5}.

Next, Claim 10 is applied with L′={ℓ2,ℓ5}, and we have h=2,g=1. χ{ℓ2,ℓ5}−χδ⁢(N2)+χδ⁢(N1)=χ{ℓ1,ℓ2}.

Note that Φ⁢(δ⁢(Q2))={1,2}.

Q3:

χδ⁢(Q3)=χ{ℓ6,ℓ8,ℓ9,ℓ10}. In Claim 8, for j=3, we have h=7,g=5. (χδ⁢(Q3)−χδ⁢(N7)+χδ⁢(N5))= 2⁢χ{ℓ6,ℓ8}.

Next, Claim 10 is applied with L′={ℓ6,ℓ8}, and we have h=5,g=4. χ{ℓ6,ℓ8}−χδ⁢(N5)+χδ⁢(N4)=χ{ℓ2,ℓ6}.

Next, Claim 10 is applied with L′={ℓ2,ℓ6}, and we have h=3,g=2. χ{ℓ2,ℓ6}−χδ⁢(N3)+χδ⁢(N2)=χ{ℓ2,ℓ3}.

Note that Φ⁢(δ⁢(Q3))={2,3}.

5 The Capacitated Graph: Deferred Proofs

In this section, we present the proofs of Propositions 4 and 5, deferred from section 2.

Proposition 4. [Restated, see original statement.]

Each of the nested cuts δ⁢(Ni),i=1,…,n−1 and each of the Q-cuts δ⁢(Qj),j=1,…,k−1 has capacity less than λ=5.

Proof.

We examine a few cases.

Nested cut δ⁢(Ni) such that Ni does not cross any Q-set:

Then, either 2≤i≤n−2 and there is a largest index j=1,…,k−2 such that Qj is contained in Ni, or else i∈{1,(n−1)}.

If i=1, then δ⁢(Ni) has two edges, namely, (i) the E1-edge v1⁢v2 of capacity 2, and (ii) the E2-edge (of capacity one) between s=v1 and the first node of Q2; clearly, δ⁢(N1) has capacity 3<λ=5. Similarly, if i=(n−1), then δ⁢(Ni) has two edges and has capacity 3<λ=5.

Otherwise, δ⁢(Ni) has three edges, namely, (i) the E1-edge vi⁢vi+1 of capacity one, (ii) the E2-edge (of capacity one) between the last node of Qj−1 and the first node of Qj+1, and (iii) the E2-edge (of capacity one) between the last node of Qj and the first node of Qj+2, Thus, the cut δ⁢(Ni) has capacity 3<λ=5.

Nested cut δ⁢(Ni) such that Ni crosses a Q-set:

Suppose that Ni crosses Qj, where j=1,…,k−1. Clearly, the first node of Qj is in Ni and the last node of Qj is not in Ni. Note that δ⁢(Ni) has two edges, namely, the E1-edge vi⁢vi+1 of capacity 3, and the E2-edge (of capacity one) between the last node of Qj−1 and the first node of Qj+1. Thus, the cut δ⁢(Ni) has capacity 4<λ=5.

𝑸-cut δ⁢(Qj):

First, suppose that j=2,…,(k−2). Observe that δ⁢(Qj) consists of the following four unit-capacity edges. There are two edges of E1 in the cut, namely, the edge between the last node of Qj−1 and the first node of Qj, and the edge between the last node of Qj and the first node of Qj+1. Moreover, there are two edges of E2 in the cut; namely, the edge between the last node of Qj−2 and the first node of Qj, and the edge between the last node of Qj and the first node of Qj+2.

The cuts δ⁢(Q1) and δ⁢(Qk−1) have capacity four since each of these cuts has only one edge of E2 (since no E2-edge is incident to the first node of Q1 or to the last node of Qk−1), and has two edges of E1, one edge of capacity 2 (i.e., s⁢v2∈δ⁢(Q1) and vn−1⁢t∈δ⁢(Qk−1)) and the other edge of capacity one.

◀

Proposition 5. [Restated, see original statement.]

Every non-trivial cut δ⁢(S), ∅⊊S⊊V, of G that is neither a nested cut nor a Q-cut has capacity ≥λ=5.

Proof.

We denote the nodes v1,…,vn by their indices 1,…,n for this proof. (Notational remark: In this proof, the symbols ℓ1, ℓ2, etc., refer to the indices 1,…,n rather than to links in L; in fact, links are not relevant in this section.) W.l.o.g., assume that S is a set of nodes such that 1∈S (thus, S contains v1), S≠Ni,i=1,…,n−1, and S≠(V−Qj),j=1,…,k−1. Let ℓ1=1 and let r1 denote the smallest index such that r1∈S and (r1+1)∉S; note that r1 is well defined, since S≠V; possibly, r1=ℓ1. Thus, [ℓ1,…,r1] is a maximal interval contained in S. Clearly, S≠[ℓ1,…,r1], otherwise, we would have S=Nr1 (contradicting our assumption that S is not a nested set). Thus, r1≤(n−2). Let ℓ2 be the smallest index >r1 that is in S; thus, ℓ2=mini⁡{i∈S,i∈[(r1+1),…,n]}. Moreover, let r2 be the smallest index ≥ℓ2 such that either r2=n or else (r2+1)∉S; thus, r2=n if [ℓ2,…,n]⊂S, and r2=min⁡{i∈S,i+1∉S,i∈[ℓ2,…,n]} if [ℓ2,…,n]⊄S. Then, [ℓ2,…,r2] is another maximal interval contained in S. Clearly, both the E1-edges vr1⁢v(r1+1) and v(ℓ2−1)⁢vℓ2 are in δ⁢(S).

For any node i (i=1,…,n), we use q⁢(i) to denote the index of the (unique) Q-set that contains i; thus, q⁢(i)=⌈(i−1)/k2⌉.

We examine a few cases and show that δ⁢(S) has capacity ≥λ=5 in each case.

  • ■

    Node r1 is not the last node of its Q-set, Qq⁢(r1), and node ℓ2 is not the first node of its Q-set, Qq⁢(ℓ2):

    Note that r1≠s=1 and ℓ2≠t=n.

    Then the E1-edge vr1⁢v(r1+1) has capacity 3, and the E1-edge v(ℓ2−1)⁢vℓ2 has capacity 3, hence, δ⁢(S) has capacity ≥6>λ=5.

  • ■

    Node r1 is not the last node of its Q-set, Qq⁢(r1), and node ℓ2 is the first node of its Q-set, Qq⁢(ℓ2):

    Note that r1≠s=1, and, possibly, ℓ2=t=n.

    Thus, r1≥2. Then the E1-edge vr1⁢v(r1+1) has capacity 3.

    Suppose ℓ2=t=n. Then the E1-edge v(ℓ2−1)⁢vℓ2 has capacity two. Thus, δ⁢(S) has capacity ≥5=λ=5.

    Now, suppose ℓ2≠t=n. Then the E1-edge v(ℓ2−1)⁢vℓ2 has capacity one. Note that q⁢(r1)≥1 and 2≤q⁢(ℓ2)≤(k−1). We have two subcases, depending on q⁢(ℓ2)−q⁢(r1).

    q⁢(ℓ2)=q⁢(r1)+1:

    Then we have two further subcases.

    1. (i)

      First, suppose that r2=n; thus, [ℓ2,…,n] is a maximal interval contained in S. Then the last node of Qq⁢(r1) is not in S and the first node of Q(q⁢(r1)+2) is in S. Then the E2-edge between the last node of Qq⁢(r1) and the first node Q(q⁢(r1)+2) is in δ⁢(S). Thus, the cut δ⁢(S) has capacity ≥5=λ=5.

    2. (ii)

      Now, suppose that r2<n. Then the E1-edge vr2⁢v(r2+1) is in δ⁢(S), and it has capacity one or more. Thus, the cut δ⁢(S) has capacity ≥5=λ=5.

    q⁢(ℓ2)≥q⁢(r1)+2:

    Then the last node of Q(q⁢(r1)−1) is in S and the first node of Q(q⁢(r1)+1) is not in S. Then the E2-edge between the last node of Q(q⁢(r1)−1) and the first node Q(q⁢(r1)+1) is in δ⁢(S). Thus, the cut δ⁢(S) has capacity ≥5=λ=5.

  • ■

    Node r1 is the last node of its Q-set, Qq⁢(r1), and node ℓ2 is not the first node of its Q-set, Qq⁢(ℓ2):

    Possibly, r1=s=1, and recall that r1≤(n−2). Note that ℓ2≠t=n.

    First, suppose r1=1. Then the E1-edge vr1⁢v(r1+1) has capacity two, and the E1-edge v(ℓ2−1)⁢vℓ2 has capacity 3. Hence, δ⁢(S) has capacity ≥5=λ=5.

    Now, suppose r1≥2. Then, 1≤q⁢(r1)≤(k−2). Then the E1-edge vr1⁢v(r1+1) has capacity one, and the E1-edge v(ℓ2−1)⁢vℓ2 has capacity 3. Clearly, δ⁢(S) has both these edges, as well as the E2-edge between the last node of Qq⁢(r1)−1 and the node (r1+1) (first node of Qq⁢(r1)+1). Hence, δ⁢(S) has capacity ≥5=λ=5.

  • ■

    Node r1 is the last node of its Q-set, Qq⁢(r1), and node ℓ2 is the first node of its Q-set, Qq⁢(ℓ2): Possibly, r1=s=1, and recall that r1≤(n−2). Possibly, ℓ2=t=n.

    Note that q⁢(r1)≥0 and 2≤q⁢(ℓ2)≤(k).

    The E1-edge v(ℓ2−1)⁢vℓ2 has capacity one or two.

    If r1=s, then the E1-edge vr1⁢v(r1+1) has capacity two, otherwise, this edge has capacity one.

    If r1≠s, then q⁢(r1)≥1; moreover, (r1+1)∉S and (r1+1) is the first node of its Q-set, Qq⁢(r1+1); hence, the E2-edge between the last node of Q(q⁢(r1)−1) and (r1+1) is in δ⁢(S).

    At this point in the analysis, it is clear that δ⁢(S) has capacity at least 3.

    We have two subcases, depending on q⁢(ℓ2)−q⁢(r1).

    q⁢(ℓ2)≥q⁢(r1)+3:

    Then the interval [(r1+1),…,(ℓ2−1)] (which is a subset of V−S) contains two or more Q-sets. We will show that the second and the last-but-one of the Q-sets each contribute an E2-edge to δ⁢(S).

    Since r1 is the last node of its Q-set, r1∈S, and the first node of Q(q⁢(r1)+2) is not in S, the E2-edge between these two nodes is in δ⁢(S).

    Similarly, since ℓ2 is the first node of its Q-set, ℓ2∈S, and the last node of Q(q⁢(ℓ2)−2) is not in S, the E2-edge between these two nodes is in δ⁢(S).

    Thus, δ⁢(S) has capacity ≥5=λ=5.

    q⁢(ℓ2)≤q⁢(r1)+2:

    In this case, q⁢(ℓ2)=q⁢(r1)+2, since the first node of Q(q⁢(r1)+1), which is (r1+1), is not in S, and ℓ2 (which is the first node of its Q-set) is in S.

    Observe that r2≠n; that is, r2≤(n−1) and the node (r2+1) is not in S. Otherwise, we would have S=V−Q(q⁢(r1)+1), contradicting our assumption that S is not the complement of a Q-set.

    First, suppose r2=(n−1). Then δ⁢(S) has the edge v(n−1)⁢vn of capacity two. Hence, overall, δ⁢(S) has capacity ≥5=λ=5.

    Now, suppose r2≤(n−2). If the E1-edge vr2⁢v(r2+1) has capacity 3, then, overall, δ⁢(S) has capacity ≥6=λ=5. Otherwise, the E1-edge vr2⁢v(r2+1) has capacity one. Observe that the node r2 is the last node of its Q-set; moreover, the node (r2+1) is the first node of its Q-set and q⁢(r2+1)≤(k−1). If the interval [(r2+1),(r2+2),…,n] has one or more nodes of S, then δ⁢(S) has one more E1-edge (besides vr2⁢v(r2+1)) of capacity one or more, hence, overall, δ⁢(S) has capacity ≥5=λ=5. Finally, suppose that the interval [(r2+1),(r2+2),…,n] has no nodes of S. Then, the node r2 is in S and the first node of Q(q⁢(r2)+2) is not in S, hence, the E2 edge between these two nodes is in δ⁢(S). Thus, overall, δ⁢(S) has capacity ≥5=λ=5.

◀

References

  • [1] Ashkan Aazami, Joseph Cheriyan, and Bundit Laekhanukit. A bad example for the iterative rounding method for mincost k-connected spanning subgraphs. Discret. Optim., 10(1):25–41, 2013. doi:10.1016/j.disopt.2012.10.002.
  • [2] Ishan Bansal. A Global Analysis of the Primal-Dual Method for Pliable Families. CoRR, abs/2308.15714, 2024. doi:10.48550/arXiv.2308.15714.
  • [3] Ishan Bansal. A global analysis of the primal-dual method for edge augmentation problems. In Nicole Megow and Amitabh Basu, editors, Integer Programming and Combinatorial Optimization - 26th International Conference, IPCO 2025, Baltimore, MD, USA, June 11-13, 2025, Proceedings, Lecture Notes in Computer Science, pages 58–71. Springer, 2025. doi:10.1007/978-3-031-93112-3_5.
  • [4] Ishan Bansal, Joe Cheriyan, Sanjeev Khanna, and Miles Simmons. Improved approximation algorithms for capacitated network design and flexible graph connectivity. In Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis, editors, 52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, Aarhus, Denmark, July 8-11, 2025, LIPIcs, pages 20:1–20:20, n.p., 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2025.20.
  • [5] Ishan Bansal, Joseph Cheriyan, Logan Grout, and Sharat Ibrahimpur. Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions. In Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, volume 261, article 15, pages 1–19, 2023. doi:10.4230/LIPIcs.ICALP.2023.15.
  • [6] Ishan Bansal, Joseph Cheriyan, Logan Grout, and Sharat Ibrahimpur. Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions. Algorithmica, 86(8):2575–2604, 2024. doi:10.1007/s00453-024-01235-2.
  • [7] Sylvia C. Boyd, Joseph Cheriyan, Arash Haddadan, and Sharat Ibrahimpur. Approximation algorithms for flexible graph connectivity. Math. Program., 204(1):493–516, 2024. doi:10.1007/s10107-023-01961-5.
  • [8] Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, and Nitish Korula. Approximability of Capacitated Network Design. Algorithmica, 72(2):493–514, 2015. doi:10.1007/s00453-013-9862-4.
  • [9] Lisa Fleischer, Kamal Jain, and David P. Williamson. Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. J. Comput. Syst. Sci., 72(5):838–867, 2006. doi:10.1016/j.jcss.2005.05.006.
  • [10] Michel X. Goemans, Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos, and David P. Williamson. Improved Approximation Algorithms for Network Design Problems. In Proceedings of the 5th Symposium on Discrete Algorithms, pages 223–232, 1994. URL: http://dl.acm.org/citation.cfm?id=314464.314497.
  • [11] M. Hariprasad. Determinant of binary circulant matrices. Special Matrices, 7(1):92–94, 2019. doi:10.1515/spma-2019-0008.
  • [12] Kamal Jain. A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem. Combinatorica, 21(1):39–60, 2001. doi:10.1007/s004930170004.
  • [13] Guy Kortsarz, Robert Krauthgamer, and James R. Lee. Hardness of approximation for vertex-connectivity network design problems. SIAM J. Comput., 33(3):704–720, 2004. doi:10.1137/S0097539702416736.
  • [14] Lap Chi Lau, R. Ravi, and Mohit Singh. Iterative Methods in Combinatorial Optimization. Cambridge Texts in Applied Mathematics. Cambridge University Press, Cambridge, UK, 2011. doi:10.1017/CBO9780511977152.
  • [15] Zeev Nutov. Tight Analysis of the Primal-Dual Method for Edge-Covering Pliable Set Families. In Pawel Gawrychowski, Filip Mazowiecki, and Michal Skrzypczak, editors, 50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025, Warsaw, Poland, August 25-29, 2025, LIPIcs, pages 82:1–82:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.MFCS.2025.82.
  • [16] Zeev Nutov. A tight example for approximation ratio 5 for covering small cuts by the primal-dual method. CoRR, abs/2512.08350, 2025. doi:10.48550/arXiv.2512.08350.
  • [17] Miles Simmons. Cover Small Cuts and Flexible Graph Connectivity Problems. Master’s thesis, University of Waterloo, Waterloo, ON, Canada, September 2025. URL: https://hdl.handle.net/10012/22426.
  • [18] Miles Simmons, Ishan Bansal, and Joe Cheriyan. A 5-Approximation Analysis for the Cover Small Cuts Problem. CoRR, abs/2602.01462, 2026. doi:10.48550/arXiv.2602.01462.
  • [19] David P. Williamson, Michel X. Goemans, Milena Mihail, and Vijay V. Vazirani. A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems. Combinatorica, 15(3):435–454, 1995. doi:10.1007/BF01299747.