Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions

We address long-standing open questions raised by Williamson, Goemans, Vazirani and Mihail pertaining to the design of approximation algorithms for problems in network design via the primal-dual method (Williamson et al. in Combinatorica 15(3):435–454, 1995. https://doi.org/10.1007/BF01299747). Williamson et al. prove an approximation ratio of two for connectivity augmentation problems where the connectivity requirements can be specified by uncrossable functions. They state: “Extending our algorithm to handle non-uncrossable functions remains a challenging open problem. The key feature of uncrossable functions is that there exists an optimal dual solution which is laminar ... A larger open issue is to explore further the power of the primal-dual approach for obtaining approximation algorithms for other combinatorial optimization problems.” Our main result proves that the primal-dual algorithm of Williamson et al. achieves an approximation ratio of \(16\) for a class of functions that generalizes the notion of an uncrossable function. There exist instances that can be handled by our methods where none of the optimal dual solutions has a laminar support. We present three applications of our main result to problems in the area of network design. (1)  A \(16\)-approximation algorithm for augmenting a family of small cuts of a graph G. The previous best approximation ratio was \(O(\log {|V(G)|})\). (2)  A \(16\cdot {\lceil k/u_{min} \rceil }\)-approximation algorithm for the Cap-k-ECSS problem which is as follows: Given an undirected graph \(G = (V,E)\) with edge costs \(c \in {\mathbb {Q}}_{\ge 0}^E\) and edge capacities \(u \in {\mathbb {Z}}_{\ge 0}^E\), find a minimum-cost subset of the edges \(F\subseteq E\) such that the capacity of any cut in (V, F) is at least k; \(u_{min}\) (respectively, \(u_{max}\)) denotes the minimum (respectively, maximum) capacity of an edge in E, and w.l.o.g. \(u_{max} \le k\). The previous best approximation ratio was \(\min (O(\log {|V|}), k, 2u_{max})\). (3)  A \(20\)-approximation algorithm for the model of (p, 2)-Flexible Graph Connectivity. The previous best approximation ratio was \(O(\log {|V(G)|})\), where G denotes the input graph.

We thank the anonymous reviewers and the ICALP PC for their comments. We are grateful to Cedric Koh and Madison Van Dyk for reading a preliminary version, and for their detailed comments and feedback. A preliminary version of this paper appeared in the Proceedings of the 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), Ed. K.Etessami, U.Feige, and G.Puppis https://drops.dagstuhl.de/opus/volltexte/2023/18067/ (LIPIcs, Volume 261, Article No. 15, pp. 15:1–15:19), [38].

The first author is partially supported by Office of Naval Research (ONR) Grant N00014-21-1-2575. The second author is supported in part by NSERC, RGPIN-2019-04197. The fourth author received funding from the following sources: NSERC grant 327620-09 and an NSERC DAS Award, European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement no. ScaleOpt-757481), and Dutch Research Council NWO Vidi Grant 016.Vidi.189.087.

Authors and Affiliations

1. Operations Research and Information Engineering, Cornell University, Ithaca, NY, USA

   Ishan Bansal & Logan Grout

2. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada

   Joseph Cheriyan

3. Department of Mathematics, London School of Economics and Political Science, London, UK

   Sharat Ibrahimpur

Contributions

All authors contributed to the research and the writing, in varying amounts. All authors reviewed the manuscript.

Corresponding author

Correspondence to Joseph Cheriyan.

Conflict of interest

The authors have no Conflict of interest to declare that are relevant to the content of this article.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Pliable Families: An Example

In Sect. 3, we showed an approximation ratio of O(1) for the WGMV primal-dual method applied to any \(f\text {-connectivity~problem}\) where f is a pliable function satisfying property \((\gamma )\). A natural question arises: Is property \((\gamma )\) essential for this result? In other words, does the WGMV primal-dual method for the \(f\text {-connectivity~problem}\) where f is a pliable function achieve an approximation ratio of O(1)? The next construction shows that the answer is no; thus, property \((\gamma )\) is essential for our results in Sect. 3.

Recall that a family of sets \(\mathcal {F}\subseteq 2^V\) is called a pliable family if \(A, B \in \mathcal {F}\) implies that at least two of the four sets \(A\cup {B}, A\cap {B}, A\setminus {B}, B\setminus {A}\) also belong to \(\mathcal {F}\).

Top: A bad example for the primal-dual method for augmenting a pliable family. Bottom: Edges of type (A) and type (B) in a bad example for the primal-dual method for augmenting a pliable family

Full size image

Now, we describe the construction: We have node-sets \(C_{ij}\) for \(i=1,2,\ldots ,k\) and \(j=0,1,2,\ldots ,k\). All these C-sets are pair-wise disjoint. Additionally, for \(j'=1,\ldots , k\), we have node-sets \(T_{1j'} \subsetneq T_{2j'}\subsetneq \cdots T_{kj'}\) and each of these are disjoint from all the C-sets. Additionally, we have at least one node \(v_0\) lying outside the union of all these C-sets and T-sets. See Fig. 3. We designate \(\mathcal {F'}\) to be the following family of node-sets that consists of two types of sets:

Informally speaking, the sets \(C_1,C_2,\dots ,C_k\) can be viewed as (pairwise-disjoint) “cylinders”, see Fig. 3, the (first) index i is associated with one of these cylinders, and note that \(C_{i0} = C_i {\setminus } (\cup _{j=1}^k C_{ij})\); the (second) index j is associated with a “layer” (i.e., a horizontal plane), and the sub-family \(T_{1j'} \subsetneq T_{2j'}\subsetneq \cdots T_{kj'}\) forms a nested family on layer \(j'\), see Fig. 3. For notational convenience, let \(T_{0j'}=\emptyset ,\; \forall j'\in [k]\). Observe that a set of type (II) is the union of one set \(T_{i'j'}\) of the nested family of layer \(j'\) together with the sets of an arbitrary sub-family of each of the “cylinder families” \(\{ C_{i0}, C_{i1}, C_{i2}, \dots , C_{ik} \}\) with (first) index \(i < i'\). We claim that the family \(\mathcal {F'}\) satisfies the condition of Lemma 2.3. Indeed consider \(A,B \in \mathcal {F'}\). If A and B are of type (I), then they are disjoint. If A is of type (I) and B is of type (II) such that \(A\cap {B}\not =\emptyset \), then \(A\cup B\) and \(B{\setminus }{A}\) are sets of type (II) so both belong to \(\mathcal {F'}\). If A and B are of type (II) such that both have the same (second) index \(j'\), then both \(A\cup {B}\) and \(A\cap {B}\) are sets of type (II). On the other hand, if A and B are of type (II) such that the (second) index \(j'\) is different for A, B, then \(A\setminus {B}\) and \(B\setminus {A}\) are sets of type (II). Thus, by Lemma 2.3, adding in all the complements of the sets of this family gives us a pliable family \(\mathcal {F}\).

The edges of the graph are of two types:

1. (A)

   For \(i' = 1,\ldots ,k\) and \(j' = 1,\ldots , k\), we have an edge from \(T_{i'j'} \setminus T_{(i'-1)j'}\) to \(C_{ij}\) where \(i=i'\) and \(j=j'\).

2. (B)

   For \(j=1,\ldots , k\), we have an edge from \(v_0\) to \(T_{1j}\). For \(i=1,\ldots ,k\), we have an edge from \(v_0\) to \(C_{i0}\).

When the primal-dual algorithm is applied to this instance, then it picks all the edges of type (A); note that there are \(k^2\) edges of type (A). Let us sketch the working of the primal-dual algorithm on this instance.

• Initially, the active sets are the type (I) sets \(C_1,\dots ,C_k\) and the smallest T-sets \(T_{11},\dots ,T_{1k}\). The algorithm increases the dual variables of each of these sets by 1/2 and then picks all the type (A) edges between \(T_{1j}\) and \(C_{1j}\) for \(j\in [k]\).

• In the next iteration, the (new) active sets are the type (I) sets \(C_2,\dots ,C_k\) and the type (II) sets of the form \(T_{2j} \cup C_{1j}\) for \(j\in [k]\). The algorithm increases the dual variables of each of these sets by 1/4 and then picks all the type (A) edges between \(T_{2j}\) and \(C_{2j}\) for \(j\in [k]\).

• Similarly, in the \(i^{th}\) iteration, the active sets are the type (I) sets \(C_i,\dots ,C_k\) and the type (II) sets of the form \(T_{ij} \cup C_{1j} \cup \dots \cup C_{(i-1)j}\) for \(j\in [k]\). The algorithm increases the dual variables of each of these sets by \(1/2^i\) and then picks all the type (A) edges between \(T_{ij}\) and \(C_{ij}\) for \(j\in [k]\).

• Finally, the reverse-delete step does not delete any edge, because the edges of type (A) form an inclusion-wise minimal solution.

On the other hand, all the edges of type (B) form a feasible solution of this instance, and there are \(\le 2k\) such edges. In more detail, each of the type (I) sets \(C_i\) is covered by the type (B) edge between \(v_0\) and \(C_{i0}\), and each of the type (II) sets containing \(T_{i'j'}\) is covered by the type (B) edge between \(v_0\) and \(T_{1j'}\). Thus, the optimal solution picks \(\le 2k\) edges.

Missing Proofs from Sect. 3

This section has several lemmas and proofs from Sect. 3 that are used to prove our main result, Theorem 1.1.

Lemma B.1

Suppose \(S_1\) is a witness for edge \(e_1\) and \(S_2\) is a witness for edge \(e_2\) such that \(S_1\) overlaps \( S_2\). Then there exist \(S_1'\) and \(S_2'\) satisfying the following properties:

1. (i)

   \(S_1'\) is a valid witness for edge \(e_1\), \(S_2'\) is a valid witness for edge \(e_2\), and \(S_1'\) does not overlap \(S_2'\).

2. (ii)

   \(S_1',S_2' \in \{S_1,S_2,S_1\cup S_2, S_1\cap S_2, S_1{\setminus } S_2, S_2{\setminus } S_1\}\).

3. (iii)

   either \(S_1' = S_1\) or \(S_2' = S_2\).

Proof

We prove the lemma via an exhaustive case analysis. Note that at least two of the four sets \(S_1\cup S_2, S_1\cap S_2, S_1{\setminus } S_2, S_2{\setminus } S_1\) must be violated in the current iteration. Moreover, observe that \(e_1\in \delta _E(S_1\setminus {S_2})\) or \(e_1\in \delta _E(S_1\cap {S_2})\), and in the latter case \(e_1\in E(S_1\cap {S_2}, V\setminus (S_1\cup {S_2}))\) or \(e_1\in E(S_1\cap {S_2}, S_2\setminus {S_1})\). We consider the following cases.

1. 1.

   If \(S_1 \cup S_2\) and \(S_1 \cap S_2\) are violated or \(S_1{\setminus } S_2\) and \(S_2{\setminus } S_1\) are violated, then the proof of Lemma 5.2 in [5] can be applied.

2. 2.

   Suppose \(S_1 \cap S_2\) is violated, and one of \(S_1\setminus {S_2}\) or \(S_2\setminus {S_1}\) is violated. W.l.o.g. suppose \(S_1 \cap S_2\) and \(S_1\setminus {S_2}\) are violated (the other case is similar). Consider where the end-nodes of the edge \(e_1\) lie. If \(e_1\in \delta _E(S_1\setminus {S_2})\), then fix \(S_1':=S_1\setminus {S_2}\) and \(S_2':=S_2\); otherwise, \(e_1\in \delta _E(S_1\cap {S_2})\), and then fix \(S_1':=S_1\cap {S_2}\) and \(S_2':=S_2\).

3. 3.

   Suppose \(S_1 \cup S_2\) is violated, and one of \(S_1\setminus {S_2}\) or \(S_2\setminus {S_1}\) is violated. W.l.o.g. suppose \(S_1 \cup S_2\) and \(S_1\setminus {S_2}\) are violated (the other case is similar). Consider where the end-nodes of the edges \(e_1\) and \(e_2\) lie. If \(e_1\in \delta _E(S_1\setminus {S_2})\), then fix \(S_1':=S_1\setminus {S_2}\) and \(S_2':=S_2\); similarly, if \(e_1\in E(S_1\cap {S_2}, V\setminus (S_1\cup {S_2}))\), then fix \(S_1':=S_1\cup {S_2}\) and \(S_2':=S_2\); finally, if \(e_1\in E(S_1\cap {S_2}, S_2\setminus {S_1})\), then fix \(S_1':=S_1\), and then if \(e_2\in \delta _E(S_1\cup {S_2})\), then fix \(S_2':=S_1\cup {S_2}\), otherwise, fix \(S_2':=S_1\setminus {S_2}\).

This completes the proof of the lemma. \(\square \)

Lemma B.2

Suppose a set \(A_1\) overlaps a set \(A_2\) and a third set \(A_3\) does not overlap \(A_1\) nor \(A_2\). Then \(A_3\) does not overlap any of the sets \(A_1\cup A_2, A_1\cap A_2, A_1 {\setminus } A_2, A_2{\setminus } A_1\).

Proof

Note that since \(A_3\) does not overlap \(A_1\) (or \(A_2\)), they are either disjoint or one contains the other. We consider the following cases.

1. 1.

   Suppose \(A_3 \cap A_1 = \emptyset \). Then \(A_2\not \subseteq A_3\) since \(A_1 \cap A_2 \ne \emptyset \). If \(A_3 \cap A_2 = \emptyset \), then \(A_3 \subseteq V{\setminus } A_1\cup A_2\) and we are done. Finally if \(A_3 \subseteq A_2\), then \(A_3 \subseteq A_2{\setminus } A_1\) and we are done.

2. 2.

   Suppose \(A_1 \subseteq A_3\). Then \(A_3 \cap A_2 \ne \emptyset \) since \(A_1\cap A_2 \ne \emptyset \). Also, \(A_3\not \subseteq A_2\) since \(A_1\not \subseteq A_2\). If \(A_2 \subseteq A_3\), then \(A_1\cup A_2 \subseteq A_3\) and we are done.

3. 3.

   Suppose \(A_3 \subseteq A_1\). Then \(A_2\not \subseteq A_3\) since \(A_2\setminus {A_1}\ne \emptyset \). If \(A_3 \subseteq A_2\), then \(A_3\subseteq A_1\cap A_2\) and we are done. Finally if \(A_3\cap A_2 = \emptyset \), then \(A_3 \subseteq A_1 {\setminus } A_2\) and we are done.

\(\square \)

Lemma 3.2. There exists a laminar family of witness sets.

Proof

We show that any witness family can be transformed to a laminar family by repeatedly applying Lemma B.1. We prove this by induction on the size of the witness family \(\ell \).

Base Case: Suppose \(\ell = 2\), then one application of Lemma B.1 is sufficient.

Inductive Hypothesis: If \(S_1,\ldots , S_\ell \) are witness sets for edges \(e_1,\ldots , e_\ell \) respectively with \(\ell \le k\), then, by repeatedly applying Lemma B.1, one can construct witness sets \(S'_1,\ldots , S'_\ell \) for the edges \(e_1,\ldots , e_\ell \) respectively such that \(S'_1,\ldots , S'_\ell \) is a laminar family.

Inductive Step: Consider \(k+1\) witness sets \(S_1,\ldots , S_{k+1}\). By the inductive hypothesis, we can repeatedly apply Lemma B.1 to all the witness sets \(S_1,\ldots , S_k\) and obtain witness sets \(S_1',\ldots , S_k'\) that form a laminar family. We now consider the following cases.

1. 1.

   If \(S_{k+1}\) does not overlap some \(S_i'\), say \(S_1'\), then we can apply the inductive hypothesis to the k sets \(S_2',\ldots , S_k', S_{k+1}\) and we obtain a laminar family of witness sets, none of which overlap \(S_1'\) either (by Lemma B.2) and so we are done.

2. 2.

   Suppose \(S_{k+1}\) overlaps all the sets \(S_1',\ldots , S_k'\) and for some \(S_i'\), say \(S_1'\), applying Lemma B.1 to the pair \(S_1',S_{k+1}\) gives \(S_1', S_{k+1}'\). Then \(S_1'\) does not overlap any of the witness sets \(S_2',\ldots , S_{k+1}'\), hence, applying the inductive hypothesis to these k sets gives us a laminar family of witness sets \(S_2^{''},\ldots , S_k^{''}\). By Lemma B.2, \(S_1'\) does not overlap any of the sets \(S_2^{''},\ldots , S_k^{''}\) and so we are done.

3. 3.

   Suppose \(S_{k+1}\) overlaps all the sets \(S_1',\ldots , S_k'\) and, for every \(S_i'\), applying Lemma B.1 to the pair \(S_i', S_{k+1}\) gives \(S''_i, S_{k+1}\). Then after doing this for every \(S_i'\), we end up with the witness family \(S_1^{''}, \ldots , S_k^{''}, S_{k+1}\) with the property that \(S_{k+1}\) does not overlap any of the other sets. Applying the inductive hypothesis to the k sets \(S_1^{''}, \ldots , S_k^{''}\) gives us a laminar family of witness sets \(S_1^{'''},\ldots , S_k^{'''}\). By Lemma B.2, \(S_{k+1}\) does not overlap any of the sets \(S_1^{'''},\ldots , S_k^{'''}\) and so we are done.

\(\square \)

Proof of Lemma 6.1 from Sect. 6

This section has a proof of Lemma 6.1. This proof is the same as the proof we posted on Arxiv in 2022, [29].

Lemma 6.1. f is a pliable function that satisfies property \((\gamma )\). Moreover, for even p, f is an uncrossable function.

Proof

Consider two violated sets \(A, B \subsetneq V\). W.l.o.g. we may assume that both A and B contain a fixed node \(r \in V\). If A, B do not cross, then it is easily seen that \(f(A)+f(B) = \max ( f(A\cap {B})+f(A\cup {B}),\; f(A\setminus {B})+f(B\setminus {A}) )\), hence, the inequality for pliable functions holds for A, B. Thus, we may assume that A, B cross. The following equations hold, see Frank’s book [35, Chapter 1.2]:

Since \(|\delta (S)|\ge {p}, \forall \emptyset \ne {S}\subsetneq {V}\), equations (2), (3) and (4) imply that \(|\delta (A \cup B)|, |\delta (A \cap B)|, |\delta (A {\setminus } B)|, |\delta (B {\setminus } A)| \in \{p,p+1,p+2\}\), and, moreover, \(|F(A \setminus B, B \setminus A)| \le {1},\, |F(A \cap B, {V\setminus (A \cup B)})| \le {1}\).

Furthermore, the above four equations imply the following parity-equations (equations (6), (7) and (8) follow from equations (3), (4) and (5), respectively).

Case 1 (of proof of the lemma): Suppose that p is even. Then the parity-equations (6)–(8) imply that among the two pairs of cuts \(\{\delta (A\cup {B}), \delta (A\cap {B})\}\) and \(\{\delta (A\setminus {B}), \delta (B\setminus {A})\}\), one of the pairs consists of two \((p+1)\)-cuts, and the other pair has at least one cut of size p. Since F is a feasible solution of \((p,1)\textrm{-FGC}\), every p-cut of (V, F) consists of safe edges (that is, a p-cut cannot contain any unsafe edge). Since A and B are violated sets, each of the cuts \(\delta (A)\) and \(\delta (B)\) contains at least two unsafe edges.

Claim C.1

Each cut \(\delta (S)\) of the pair of \((p+1)\)-cuts \(\{\delta (A\cup {B}), \delta (A\cap {B})\}\) or \(\{\delta (A\setminus {B}), \delta (B\setminus {A})\}\) (obtained from A, B) also contains at least two unsafe edges, and so S is a violated set for each of these cuts.

We prove this claim by a simple case analysis on the end-nodes of the unsafe edges of the cuts \(\delta (A)\) and \(\delta (B)\). W.l.o.g. assume that \(\delta (A\cup {B})\) and \(\delta (A\cap {B})\) are \((p+1)\)-cuts and that \(\delta (A\setminus {B})\) is a p-cut. The other cases are handled similarly. Clearly, \(\delta (A\setminus {B})\) has no unsafe edges. Since A is a violated set, either (i) \(F(A\cap B, B\setminus {A})\) has two unsafe edges or (ii) \(F(A\cap B, B\setminus {A})\) has one unsafe edge and \(F(A\cap B, {V\setminus (A\cup B)})\) has one unsafe edge (recall that the size of the latter edge-set is \(\le 1\)). Since B is a violated set, either (iii) \(F(B\setminus {A}, {V\setminus (A\cup {B})})\) has two unsafe edges or (iv) \(F(B\setminus {A}, {V\setminus (A\cup B)})\) has one unsafe edge and \(F(A\cap B, {V\setminus (A\cup B)})\) has one unsafe edge. Now, observe that both \(A\cap {B}\) and \(A\cup {B}\) are violated sets, because, by (i) or (ii), \(\delta (A\cap {B})\) has at least two unsafe edges, and, by (iii) or (iv), \(\delta (A\cup {B})\) has at least two unsafe edges. (If both \(\delta (A\setminus {B})\) and \(\delta (B\setminus {A})\) are \((p+1)\)-cuts, and there are no unsafe edges in either \(\delta (A\cap {B})\) or \(\delta (A\cup {B})\), then both \(\delta (A\setminus {B})\) and \(\delta (B\setminus {A})\) have \(\ge 2\) unsafe edges, so both \(A\setminus {B}\) and \(B\setminus {A}\) are violated sets.) This proves the claim.

Therefore, when p is even, the function f is an uncrossable function (recall that every uncrossable function is a pliable function that satisfies property \((\gamma )\)).

Case 2 (of proof of the lemma): Suppose that p is odd. Then we have \( |\delta (A \cup B)| \equiv |\delta (A \cap B)| \equiv |\delta (A\setminus {B})| \equiv |\delta (B\setminus {A})| \quad (\text {mod} \, 2)\). Hence, the above equations (2)–(5) and parity-equations (6)–(8) imply that either all four cuts \(\delta (A\cup {B}), \delta (A\cap {B}), \delta (A\setminus {B}), \delta (B\setminus {A})\) are \((p+1)\)-cuts, or at least one cut from each pair \(\{\delta (A\cup {B}), \delta (A\cap {B})\}\) and \(\{\delta (A\setminus {B}), \delta (B\setminus {A})\}\) is a p-cut.

Claim C.2

Suppose that at least one cut from each pair \(\{\delta (A\cup {B}), \delta (A\cap {B})\}\) and \(\{\delta (A\setminus {B}), \delta (B\setminus {A})\}\) is a p-cut. Then either A is not a violated set, or B is not a violated set.

To prove this claim, let us assume that \(|\delta (A\setminus {B})|=p\); similar arguments apply for the other case. The edge-set F is feasible for \((p,1)\textrm{-FGC}\), hence, all edges of \(\delta (A\setminus {B})\) are safe. Moreover, one of the cuts \(\delta (A\cap {B})\) or \(\delta (A\cup {B})\) has size p and consists of safe edges. If \(|\delta (A\cap {B})|=p\), then the cut \(\delta (A)\) consists of safe edges (since \(\delta (A)\subseteq \delta (A\cap {B})\cup \delta (A\setminus {B})\)), hence, A cannot be a violated set. Otherwise, if \(|\delta (A\cup {B})|=p\), then the cut \(\delta (B)\) consists of safe edges (since \(\delta (B)=\delta (V\setminus {B})\subseteq \delta (A\setminus {B})\cup \delta (V\setminus (A\cup {B}))\)), hence, B cannot be a violated set. This proves the claim.

Claim C.2 implies that all four cuts \(\delta (A\cup {B}), \delta (A\cap {B}), \delta (A\setminus {B}), \delta (B\setminus {A})\) are \((p+1)\)-cuts.

Claim C.3

Consider two crossing violated sets \(A, B \subseteq V\).

1. (i)

   Then each of the four cuts \(\delta (A\cup {B}), \delta (A\cap {B}), \delta (A\setminus {B}), \delta (B\setminus {A})\) has size \((p+1)\), and we have \(|F(A\setminus {B}, B\setminus {A})| = 0 = |F(A\cap {B}, V\setminus (A\cup {B}))|\).

2. (ii)

   Moreover, each of the four sets \(F(A\cap {B},\,A\setminus {B}),\; F(A\cap {B},\,B\setminus {A}),\; F(A\setminus {B},\,V\setminus (A\cup {B})),\; F(B\setminus {A},\,V\setminus (A\cup {B}))\) has size \((p+1)/2\).

Part (i) of this claim follows from the above arguments (see the discussion before and after Claim C.2). Moreover, we have \(|F(A {\setminus } B, B {\setminus } A)| = 0\) and \(|F(A \cap B, V {\setminus } (A \cup B))| = 0\) by equations (3),(4). Next, consider part (ii) of the claim. Using the first part of the claim together with equation (5), we have \(|F(A\cap {B},\,A\setminus {B})|=(p+1)/2\). Since \(\delta (A\setminus {B})\) is a \((p+1)\)-cut and it is the disjoint union of \(F(A\setminus {B},\,A\cap {B})\) and \(F(A\setminus {B},\,V\setminus (A\cup {B}))\), we have \(|F(A\setminus {B},\,V\setminus (A\cup {B}))|=(p+1)/2\). Similarly, we have \(|F(A\cap {B},\,B\setminus {A})|=(p+1)/2\), \(|F(B\setminus {A},\,V\setminus (A\cup {B}))|=(p+1)/2\). This proves the claim.

Claim C.4

1. (i)

   At least two of the four cuts \(\delta (A\cup {B}), \delta (A\cap {B}), \delta (A\setminus {B}), \delta (B\setminus {A})\) each contain at least two unsafe edges.

2. (ii)

   Moreover, if A is a minimal violated set, then \(F(B\setminus {A},\,V\setminus (A\cup {B}))\) has at least two unsafe edges, and each of \(F(A\cap {B},\,B\setminus {A})\) and \(F(A\setminus {B},\,V\setminus (A\cup {B}))\) has exactly one unsafe edge.

We prove this claim by a simple case analysis on the end-nodes of the unsafe edges of the cuts \(\delta (A)\) and \(\delta (B)\). Observe that \(|F(A {\setminus } B, B {\setminus } A)| = 0\) and \(|F(A \cap B, V {\setminus } (A \cup B))| = 0\), by equations (3),(4). Each edge of \(\delta (A)\) is in exactly one of the sets \(F(A\cap {B},\,B\setminus {A})\) or \(F(A\setminus {B},\,V\setminus (A\cup {B}))\); call these edge-sets \(\phi _1, \phi _2\) for notational convenience. Similarly, each edge of \(\delta (B)\) is in exactly one of the sets \(F(A\cap {B},\,A\setminus {B})\) or \(F(B\setminus {A},\,V\setminus (A\cup {B}))\); call these edge-sets \(\phi _3, \phi _4\) for notational convenience. If two of the unsafe edges of \(\delta (A)\) are in the same set (i.e., if \(\phi _1\) or \(\phi _2\) has two unsafe edges), then part (i) of the claim holds, since either \(\delta (A\cap {B}), \delta (B\setminus {A})\) each have two (or more) unsafe edges or else \(\delta (A\cup {B}), \delta (A\setminus {B})\) each have two (or more) unsafe edges. Similarly, if two of the unsafe edges of \(\delta (B)\) are in the same set (i.e., if \(\phi _3\) or \(\phi _4\) has two unsafe edges), then part (i) of the claim holds. There is one remaining case: each of the four sets \(F(A\cap {B},\,B\setminus {A})\), \(F(A\setminus {B},\,V\setminus (A\cup {B}))\), \(F(A\cap {B},\,A\setminus {B})\), \(F(B\setminus {A},\,V\setminus (A\cup {B}))\) has exactly one unsafe edge. In this case, each of the four sets \(\delta (A\cup {B}), \delta (A\cap {B}), \delta (A\setminus {B}), \delta (B\setminus {A})\) has two unsafe edges. This proves part (i) of the claim. To prove part (ii) of the claim, observe that neither of the \((p+1)\)-cuts \(\delta (A\cap {B})\) or \(\delta (A\setminus {B})\) can have two (or more) unsafe edges, otherwise, a proper subset of the minimal violated set A would be violated. Then, the above case analysis shows that each of the two sets \(F(A\cap {B},\,B\setminus {A})\), \(F(A\setminus {B},\,V\setminus (A\cup {B}))\) has exactly one unsafe edge, and the set \(F(B\setminus {A},\,V\setminus (A\cup {B}))\) has two (or more) unsafe edges. This proves part (ii) of the claim.

Clearly, the function f is a pliable function, by Claim C.4, part (i). Next, we argue that the function f satisfies property \((\gamma )\).

Let C be a minimal violated set and let \(S_1,S_2\) be violated sets such that C crosses both \(S_1,S_2\) and \(S_1 \subsetneq S_2\). W.l.o.g. assume that \(S_2 \setminus (S_1\cup C)\) is non-empty. Since C crosses \(S_2\), the edge-set \(F(S_2\setminus {C},\,V\setminus (S_2\cup {C}))\) has size \((p+1)/2\), by Claim C.3. Moreover, by Claim C.4, part (ii), this edge-set contains two unsafe edges. Observe that \(S_1\cup {C}\) crosses \(S_2\); to see this, note that C crosses \(S_2\) so the sets \(C\cap {S_2},\, C\setminus {S_2},\, V\setminus (C\cup {S_2})\) are non-empty, and, by assumption, \(S_2 \setminus (S_1\cup C)\) is non-empty. Applying Claim C.3 to this pair of crossing sets, we see that the edge-set \(F(S_2\setminus (S_1\cup {C}),\,V\setminus (S_2\cup {C}))\) has size \((p+1)/2\). Then we have \(F(S_2\setminus {C},\,V\setminus (S_2\cup {C})) = F(S_2\setminus (S_1\cup {C}),\,V\setminus (S_2\cup {C}))\), because both edge-sets have the same size and one edge-set is a subset of the other edge-set. Hence, \(F(S_2\setminus (S_1\cup {C}),\,V\setminus (S_2\cup {C}))\) contains two unsafe edges. Finally, by Claim C.3, the cut \(\delta (S_2\setminus (S_1\cup {C}))\) has size \((p+1)\). Since this cut has two (or more) unsafe edges, \(S_2\setminus (S_1\cup {C})\) is a violated set. This proves that the function f satisfies property \((\gamma )\).

This completes the proof of Lemma 6.1. \(\square \)

Optimal Dual Solutions with Non-laminar Supports

In this section, we describe an instance of the \(\textrm{AugSmallCuts}\) problem where none of the optimal dual solutions (to the dual LP given in (2.2), Sect. 2) have a laminar support. Recall that the connectivity requirement function f for the \(\textrm{AugSmallCuts}\) problem is pliable and satisfies property \((\gamma )\), as seen in the proof of Theorem 1.2.

Consider the graph \(G = (V,E)\) (shown in Fig. 4 below using solid edges) which is a cycle on 4 nodes 1, 2, 3, 4, in that order. Edge-capacities are given by \(u_{12}=3, u_{23}=4, u_{34}=2, u_{41}=1\). The link-set (shown using dashed edges) is \(L=\{ 12, 23, 34, 41 \}\), which is a disjoint copy of E. Link-costs are given by \(c_{12} = c_{23} = c_{34} = 1\) and \(c_{41} = 2\).

An instance of the \(\textrm{AugSmallCuts}\) problem where every optimal dual solution has non-laminar support

Full size image

Consider the \(\textrm{AugSmallCuts}\) instance that arises when we choose \(\widetilde{\lambda }= 6\). The family of small cuts (with capacity strictly less than \(\widetilde{\lambda }\)) is given by , where

The associated pliable function f satisfies \(f(S) = 1\) if and only if or holds. Observe that f is not uncrossable since \(f(\{1,2\}) = 1 = f(\{2,3\})\), but \(f(\{1,2\} \cap \{2,3\}) = f(\{2\}) = 0\) and \(f(\{2,3\} \setminus \{1,2\}) = f(\{3\}) =0\). Also note that the minimal violated set \(\{2,3\}\) (w.r.t. \(F = \emptyset \)) crosses the violated set \(\{1,2\}\).

It can be seen that there are three inclusion-wise minimal link-sets that are feasible for the above instance and these are given by

Since each \(F \in \mathcal {C}\) has cost 3, the optimal value for the instance is 3. Next, since L contains at least two links from every nontrivial cut, the vector \(x\in [0,1]^L\) with \(x_e=\frac{1}{2},\,\forall {e}\in {L}\) is a feasible augmentation for the fractional version of the instance, i.e., x is feasible for the primal LP given in (2.2), Sect. 2. Therefore, the optimal value of the primal LP is at most \(\frac{5}{2}\).

Now, consider the dual LP, which is explicitly stated below. The dual packing-constraints are listed according to the following ordering of the links: 12, 23, 34, 41. For notational convenience, we use the shorthand \(y_1\) to denote the dual variable \(y_{\{1\}}\) corresponding to the set \(\{1\}\). We use similar shorthand to refer to the dual variables of the other sets; thus, \(y_{234}\) refers to the dual variable \(y_{\{2,3,4\}}\), etc.

Observe that adding all packing constraints gives , hence, the optimal value of the dual LP is at most 5/2. Moreover, a feasible dual solution with objective 5/2 must satisfy the following conditions:

Clearly, there is at least one solution to the above set of equations, hence, by LP duality, the optimal value of both the primal LP and the dual LP is 5/2.

Furthermore, any optimal dual solution \(y^*\) satisfies \(\max (y^*_S,y^*_{V\setminus {S}}) > 0\) for all (by the above set of equations). We conclude by arguing that for any optimal dual solution \(y^*\), its support is non-laminar, because some two sets cross. Since the relation A crosses B is closed under taking set-complements (w.r.t. the ground-set V), we may assume w.l.o.g. that the support contains each set in . The support of \(y^*\) is not laminar because \(\{1,2\}\) and \(\{2,3\}\) cross.

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions