A Bad Example for Jain’s Iterative Rounding Theorem for the Cover Small Cuts Problem
Abstract
The problem is a key problem in Network Design. In the problem, we are given a capacitated (undirected) graph and a threshold value , as well as a set of links with end-nodes in and a non-negative cost for each link ; 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 there exists a variable that has value at least a constant (e.g., ).
We construct an example showing that this property fails to hold for the standard LP relaxation of the problem. This indicates that the polyhedron of feasible solutions to the LP (for ) 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 approximation algorithm for .
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 for the problem. That is, the WGMV primal-dual algorithm, applied to the same LP relaxation, finds an integer solution of cost times the optimal value of the LP.
Keywords and phrases:
approximation algorithms, capacitated network design, covering small cuts, edge-connectivity of graphs, -connectivity problem, iterative rounding method, primal-dual methodCategory:
APPROXFunding:
Ishan Bansal: This work is external and does not relate to the position at Amazon.Copyright and License:
2012 ACM Subject Classification:
Theory of computation Approximation algorithms analysisAcknowledgements:
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 GurSeries and Publisher:
Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik
1 Introduction
The 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 problem, we are given a capacitated (undirected) graph and a threshold value , as well as a set of links with end-nodes in and a non-negative cost for each link ; 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 of links is said to cover a node-set if there exists a link with exactly one end-node in , and the objective is to find a minimum-cost that covers each nonempty such that . 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 for this problem. Later, Bansal [2, 3] and Nutov [15] proved that the same algorithm achieves approximation ratio . Simmons et al. [18, 17] improved the approximation ratio to . Recently, Nutov [16] constructed an example of the problem such that the WGMV primal-dual algorithm finds a solution of cost , where opt denotes the cost of an optimal (integral) solution and is an arbitrarily small number. This shows that the -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 as an abbreviation for “the problem”.
Given a graph 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--ECSS problem sits in the core of capacitated network design. In this problem, we are given an (undirected) graph , 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 or more. Let and let (respectively, ) denote the minimum (respectively, maximum) capacity of an edge; assume that . One of the earliest approximation algorithms for Cap--ECSS is due to Goemans et al. [10], and it achieves an approximation ratio of . Over the last three decades, there have been several advances, and the best approximation ratio known is , 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--ECSS are based on approximation algorithms for .
For the benefit of readers who are not familiar with the papers cited above, let us sketch a simple reduction from Cap--ECSS to that incurs a multiplicative factor of 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 to be the empty set; during the execution of the algorithm, is our current “solution graph.” While the minimum capacity of a cut in is less than , run an -approximation algorithm for with input and with link-set , to augment all cuts with and obtain a valid augmentation . Update by adding , that is, . On exiting the while loop, output the edge-set . Bansal et al. [6, Theorem 1.3] show that the cost of is , where opt denotes the optimal cost for the Cap--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 -connectivity. In this problem, we are given an undirected graph on nodes with nonnegative costs on the edges and a requirement function on subsets of nodes. The algorithmic goal is to find an edge-set with minimum cost such that for all cuts , we have . A function is called weakly supermodular if , and for all , either , or . The following is an LP relaxation for the -connectivity problem.
| (LP: f-connectivity) | |||||
| subject to: | |||||
Assuming that the function is weakly supermodular, integral, and has a positive value for some , Jain [12] presented a 2-approximation algorithm for the -connectivity problem, based on the following key result.
Theorem 1 (Jain [12, Theorem 3.1]).
Assume that the function is weakly supermodular, integral, non-negative and non-zero. Then, in any basic feasible solution to the LP relaxation, for at least one edge, , is at least .
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 such that every basic feasible solution of the LP relaxation has an entry such that (i.e., the infinity norm of 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 problem, and we mention that the WGMV primal-dual algorithm applied to the same LP relaxation finds an integer solution of cost . This indicates that the polyhedron of feasible solutions to the LP relaxation (for ) 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 approximation algorithm for .
Consider an instance of the problem. Let . Then we have the following covering LP relaxation of the problem.
| (LP: Cover Small Cuts) | |||||
| subject to: | |||||
Remark 2.
Theorem 3.
Let be an even integer. There is an instance of the problem such that the LP relaxation (LP: Cover Small Cuts) has a basic feasible solution such that every positive variable of has value .
Discussion and contrast with previous results
Jain’s iterative rounding theorem [12] (see Theorem 1 above) asserts that for the LP relaxation of -connectivity, whenever is weakly supermodular, every basic feasible solution has at least one variable . This Jain property is the lever behind Jain’s -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 -approximation algorithm unless . 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 had some variable for a fixed positive constant , then iterating Jain’s rounding scheme would yield a polynomial-time -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 -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 -node-connected spanning subgraph problem (mincost -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 satisfying , thereby showing that the standard iterative rounding method cannot achieve an approximation ratio better than for mincost -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 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 (see (LP: Cover Small Cuts)) is a covering LP of the same type as the LP for -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 does admit a polynomial-time -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 cannot be attributed to hardness of approximation. This separates from NC-SNDP: for NC-SNDP, the Jain property fails (in part) because the problem is hard to approximate; for , the problem allows an approximation algorithm, but the known iterative rounding methods via the natural covering LP cannot achieve an 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 , we use to denote the set . A pair of subsets of (the ground-set) is said to cross if each of the four sets is nonempty.
For a graph and , the cut refers to the set of edges that have exactly one end-node in ; is called a non-trivial cut if .
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 LP to denote the optimal value of an LP relaxation. The context will resolve potential ambiguities.
2 The Capacitated Graph
Let be an even integer. The capacitated graph has nodes, and edges. The edge capacities are chosen from the set and (the threshold value for small cuts) is chosen to be .
We denote the nodes of by , as well as by the indices . For notational convenience, let and let .
The family of small cuts consists of two sub-families. One sub-family corresponds to the node-sets . In other words, for each of the sets , is a small cut. We call the sets () the nested sets. The other sub-family corresponds to the node-sets . Note that these sets form a partition of into sets, each of cardinality . In other words, for each of the “intervals” () formed by picking the node with index and the next consecutively indexed nodes, is a small cut. We call the sets () the -sets; moreover, by the first node of we mean the node of lowest index in (i.e., node ), and by the last node of we mean the node of highest index in (i.e., node ). For notational convenience, let and let ; moreover, let be the last node of and let be the first node of . Consequently, in the proofs below, may only serve as the last node of a -set, and may only serve as a first node. Thus, if we examine the case that a specified node is a first node, it is guaranteed that (i.e., the -set containing is not ); similarly, if we examine the case that a specified node is a last node, it is guaranteed that (i.e., the -set containing is not ).
For a nested set () and a -set (), observe that and ; moreover, if is nonempty, then either crosses (i.e., both and are nonempty) or .
There are two types of edges in . There are edges that form the -path ; we use to denote the edge set of this path. The first edge and the last edge of this path have capacity , thus, . Consider any other edge of this path. If both and are in the same -set then has capacity , otherwise, has capacity one. Moreover, there are other edges (that are not in the -path), and each of these edges has capacity one; we use to denote this set of edges. The nodes incident to the -th edge of () have indices and . Thus, has an edge between and the first node of , an edge between the last node of and , and, for each , has an edge between the last node of and the first node of .
The following figure illustrates the construction of the capacitated graph for ; the graph has nodes and edges.
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 and each of the -cuts has capacity less than .
Proposition 5.
Every non-trivial cut , , of that is neither a nested cut nor a -cut has capacity .
3 The Links Graph
Let denote the graph of the links; thus is the set of links, and we denote the links by the symbol , e.g., , , etc. The number of links is . The links are partitioned into internally node disjoint -paths that we denote by . The -path has one link . Each of the -paths has internal nodes and has links. Moreover, the sequence of node indices of each of these -paths is an increasing sequence; that is, the node sequence has the form , where . Each of the nodes is in one of the -paths ; thus, each of these nodes is incident to two links.
Recall that we have -sets, each with nodes, and -paths each with internal nodes. Each of the -paths is constructed such that it is incident to precisely one node of (of the ) -sets, and it is disjoint from the other -sets. The -path is incident to the -set with index and the next consecutively indexed -sets (with “wrap around”); thus, for and , the -path and the set have a node in common iff
If an -path and a set have a node in common, then any one node of could be assigned to ; in other words, our construction does not specify the internal nodes of , it only specifies the -sets that intersect .
Let denote the zero-one matrix that has a row for each -path and a column for each set such that the entry is one iff and have a node in common. Then, by construction, is a circulant matrix with entries of zero or one such that each row has consecutive ones (with “wrap around”) and the remaining entries of the row are zero. Observe that the number of ones in each row, , and the size of the matrix, , are relatively prime (i.e., ). For an illustration, see the example at the end of section 4.
Lemma 6.
The matrix has rank . Moreover, .
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 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 . The graph has nodes and links. The links partition into (internally node disjoint) -paths ; the links of are indicated by distinct colours.
We construct a basic feasible solution by assigning the value to each link, thus, . Informally speaking, we are assigning a value to each of the -paths . It is easy to verify that each of the small cuts, namely, and , is “tightly covered” by . First, consider a cut , and observe that each of the -paths has exactly one of its links in , hence, . Next, consider a cut , and observe that of the -paths have exactly one internal node in , hence, each of these -paths has exactly two links in , therefore, . Note that the tight constraints at are the covering constraints for the small cuts, and none of the lower bound constraints is tight (since ).
The basis matrix of has one row for each small cut and one column for each link; the entry of corresponding to a small cut and a link is one if , otherwise, the entry is zero. Thus, is an matrix with entries of zero or one; recall that . In the next section, we show that matrix has full rank, and that will prove our claim that is a basic feasible solution of the LP relaxation of .
4 The rank of the incidence matrix of small cuts and links
Let denote the zero-one incidence matrix of the small cuts and the links; is an matrix, where . The matrix has rows corresponding to the cuts of the -sets followed by rows corresponding to the cuts of the nested sets; the columns of correspond to the links. In this section, the main goal is to show that is non-zero; equivalently, has full rank. We start by fixing a convenient indexing for the rows and columns of . The rows of correspond to the cuts of , and the rows of correspond to the cuts of . The links are indexed as follows: The link of the -path incident to node is denoted ; thus, each of is in , and there is a bijection between these links and the -path . Note that each of the remaining links is incident to one of the nodes , and, for each , the unique link that is incident to node and is in the cut is assigned the index . The columns of correspond to the links .
Let us view the matrix as a block matrix where is the sub-matrix of whose rows correspond to the cuts of and whose columns correspond to the links , and is the sub-matrix of whose rows correspond to the cuts of and whose columns correspond to the links .
Claim 7.
The sub-matrix is lower-triangular and all entries on the diagonal are one; thus, .
Proof.
The link (with end nodes and ) is in each of the cuts , . For each of the links where , note that the link is in the cut and it is in none of the cuts .
Our plan is to apply row operations to the first rows of in order to transform the submatrix to a submatrix of the form where denotes the transpose of the matrix and denotes a matrix of zeros. Therefore, using row operations, we will rewrite the matrix as the block matrix then, by applying Lemma 6 as well as a result on the determinant of block matrices, we see that the determinant of the re-written matrix is .
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 let denote the zero-one row incidence vector of ; thus, for any link , iff . Note that rows of correspond to . For any link , let denote the index of the -path that contains . For each of the links , , note that , since we have a bijection between these links and the -paths . For any set of links , let denote the set of indices of the -paths that contain at least one of the links of ; thus, , and index is in iff the -path contains one of the links of . For example, if is a subset of , then .
Consider any row , of the matrix ; this row-vector is the same as . Let denote the largest index such that the nested set is disjoint from , and let denote the smallest index such that the nested set contains . (By our construction, the nodes of are in the interval .)
Claim 8.
where is the set of links in .
Proof.
By construction, every link has its two end nodes in two different -sets. Hence, every link that has its lower-index node in is in ; similarly, every link that has its higher-index node in is in . Moreover, is the set of links that have their lower-index node in and their higher-index node in . The equation in the claim follows from these statements.
In the above claim, note that is contained in the cut of a -set, hence, the link cannot be in .
Our plan is to (separately) apply the row operations described in the above claim to each of the rows of . The next lemma explains how to apply row operations to , where is any set of links contained in some nested cut and , to transform to the vector , where . Informally speaking, we can apply row operations to “map” any row vector , where and , to the row incidence vector (padded with zeros on the right) of the -paths among that contain (at least) one of the links of . Thus, by applying the above claim and the next lemma, we “map” each row of the submatrix to a distinct row of the submatrix
Lemma 9.
Let , and let be any set of links. By applying row operations, one can transform the vector to the vector , where .
Proof.
By induction on the index of the nested set whose cut contains .
Let be the smallest index such that the nested cut contains . If , then we have and the lemma is proved.
Now, suppose ; thus, contains a link with . Observe that contains the link which is incident to node and is in the cut ; informally speaking, the presence of in certifies that is contained in and is not a subset of for any . Let denote the set of links ; is a “complementary set” of links w.r.t. and . For every link , observe that (since and ).
Let be the smallest index such that the nested cut contains . Again, observe that contains the link which is incident to node and is in the cut . Clearly, and , since and .
Claim 10.
There exists a set of links of , call it , such that
-
(i)
, and
-
(ii)
.
Proof.
Observe that , and that is contained in ; also, note that is in . Let ; observe that is a set of links and . Hence, we have . This proves part (i) of the claim.
Moreover, note that each of the nested cuts contains exactly one link from each of the -paths ; that is, for each , . Hence, . 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 by the set ; note that has the properties of (listed in the lemma statement) and . Moreover, is contained in the cut of a nested set of smaller index than the index of any nested set whose cut contains .
Thus, the lemma follows by induction.
Our main result of this section follows from the above discussion.
Theorem 3. [Restated, see original statement.]
Let be an even integer. There is an instance of the problem such that the LP relaxation (LP: Cover Small Cuts) has a basic feasible solution such that every positive variable of has value .
4.1 Example with
In this subsection, we fix , 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 -paths , and the links of are , the links of are , the links of are , and has the link .
The incidence matrix of the -paths and the -sets is given below.
The incidence matrix of the small cuts and the links is given below. Note that the submatrix (of the nested cuts and the links ) is lower-triangular with diagonal entries of one.
5 The Capacitated Graph: Deferred Proofs
Proposition 4. [Restated, see original statement.]
Each of the nested cuts and each of the -cuts has capacity less than .
Proof.
We examine a few cases.
- Nested cut such that does not cross any -set:
-
Then, either and there is a largest index such that is contained in , or else .
If , then has two edges, namely, (i) the -edge of capacity , and (ii) the -edge (of capacity one) between and the first node of ; clearly, has capacity . Similarly, if , then has two edges and has capacity .
Otherwise, has three edges, namely, (i) the -edge of capacity one, (ii) the -edge (of capacity one) between the last node of and the first node of , and (iii) the -edge (of capacity one) between the last node of and the first node of , Thus, the cut has capacity .
- Nested cut such that crosses a -set:
-
Suppose that crosses , where . Clearly, the first node of is in and the last node of is not in . Note that has two edges, namely, the -edge of capacity , and the -edge (of capacity one) between the last node of and the first node of . Thus, the cut has capacity .
- -cut :
-
First, suppose that . Observe that consists of the following four unit-capacity edges. There are two edges of in the cut, namely, the edge between the last node of and the first node of , and the edge between the last node of and the first node of . Moreover, there are two edges of in the cut; namely, the edge between the last node of and the first node of , and the edge between the last node of and the first node of .
The cuts and have capacity four since each of these cuts has only one edge of (since no -edge is incident to the first node of or to the last node of ), and has two edges of , one edge of capacity (i.e., and ) and the other edge of capacity one.
Proposition 5. [Restated, see original statement.]
Every non-trivial cut , , of that is neither a nested cut nor a -cut has capacity .
Proof.
We denote the nodes by their indices for this proof. Notational remark: In this proof, the symbols , , etc., refer to the indices rather than to links in ; in fact, links are not relevant in this section. W.l.o.g., assume that is a set of nodes such that (thus, contains ), , and . Let and let denote the smallest index such that and ; note that is well defined, since ; possibly, . Thus, is a maximal interval contained in . Clearly, , otherwise, we would have (contradicting our assumption that is not a nested set). Thus, . Let be the smallest index that is in ; thus, . Moreover, let be the smallest index such that either or else ; thus, if , and if . Then, is another maximal interval contained in . Clearly, both the -edges and are in .
For any node (), we use to denote the index of the (unique) -set that contains ; thus, .
We examine a few cases and show that has capacity in each case.
-
Node is not the last node of its -set, , and node is not the first node of its -set, :
Note that and .
Then the -edge has capacity , and the -edge has capacity , hence, has capacity .
-
Node is not the last node of its -set, , and node is the first node of its -set, :
Note that , and, possibly, .
Thus, . Then the -edge has capacity .
Suppose . Then the -edge has capacity two. Thus, has capacity .
Now, suppose . Then the -edge has capacity one. Note that and . We have two subcases, depending on .
- :
-
Then we have two further subcases.
-
(i)
First, suppose that ; thus, is a maximal interval contained in . Then the last node of is not in and the first node of is in . Then the -edge between the last node of and the first node is in . Thus, the cut has capacity .
-
(ii)
Now, suppose that . Then the -edge is in , and it has capacity one or more. Thus, the cut has capacity .
-
(i)
- :
-
Then the last node of is in and the first node of is not in . Then the -edge between the last node of and the first node is in . Thus, the cut has capacity .
-
Node is the last node of its -set, , and node is not the first node of its -set, :
Possibly, , and recall that . Note that .
First, suppose . Then the -edge has capacity two, and the -edge has capacity . Hence, has capacity .
Now, suppose . Then, . Then the -edge has capacity one, and the -edge has capacity . Clearly, has both these edges, as well as the -edge between the last node of and the node (first node of ). Hence, has capacity .
-
Node is the last node of its -set, , and node is the first node of its -set, : Possibly, , and recall that . Possibly, .
Note that and .
The -edge has capacity one or two.
If , then the -edge has capacity two, otherwise, this edge has capacity one.
If , then ; moreover, and is the first node of its -set, ; hence, the -edge between the last node of and is in .
At this point in the analysis, it is clear that has capacity at least .
We have two subcases, depending on .
- :
-
Then the interval (which is a subset of ) contains two or more -sets. We will show that the second and the last-but-one of the -sets each contribute an -edge to .
Since is the last node of its -set, , and the first node of is not in , the -edge between these two nodes is in .
Similarly, since is the first node of its -set, , and the last node of is not in , the -edge between these two nodes is in .
Thus, has capacity .
- :
-
In this case, , since the first node of , which is , is not in , and (which is the first node of its -set) is in .
Observe that ; that is, and the node is not in . Otherwise, we would have , contradicting our assumption that is not the complement of a -set.
First, suppose . Then has the edge of capacity two. Hence, overall, has capacity .
Now, suppose . If the -edge has capacity , then, overall, has capacity . Otherwise, the -edge has capacity one. Observe that the node is the last node of its -set; moreover, the node is the first node of its -set and . If the interval has one or more nodes of , then has one more -edge (besides ) of capacity one or more, hence, overall, has capacity . Finally, suppose that the interval has no nodes of . Then, the node is in and the first node of is not in , hence, the edge between these two nodes is in . Thus, overall, has capacity .
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.
