In this paper
AbstractIntroductionResultsTechniques and AI DisclosureHardnesss and InapproximabilityApproximation AlgorithmsKey Technical LemmaAugmentation CostBipartite GraphsNon-Bipartite GraphsFlexible Graph Connectivity via Disjunctive ProgrammingAppendixIntegrality Gap of (LP1)Tight example for the naive greedy heuristicReferencesWorksComputer Science
Flexible Edge Cover: A Disjunctive Programming driven Approximation
Abstract
We introduce the flexible edge cover problem, denoted FLEX-EDGE-COVER: the input here is an undirected graph with non-negative edge costs along with a partition of the edges into safe and unsafe edges, non-negative integers and , and the goal is to find a minimum cost subset of edges such that each vertex has either at least safe edges incident to it or at least total edges incident to it. We show that FLEX-EDGE-COVER is APX-hard in simple bipartite graphs. A greedy approach leads to a -approximation in all graphs. We show that the -factor can be improved in simple graphs via a novel disjunctive programming-based LP formulation. AI-tools were used in the analysis of our rounding algorithm. Our motivation for introducing and investigating FLEX-EDGE-COVER is its close connection to the Flexible Graph Connectivity problem (denoted -FGC) which has garnered much recent attention. For -FGC, we develop a tighter LP-formulation via the disjunctive programming approach. We hope that our disjunctive-programming based LP and rounding algorithms for FLEX-EDGE-COVER will serve as a starting point towards a constant factor approximation for -FGC.
Introduction
Edge-Cover is a classic problem in combinatorial optimization that aims to find a minimum cost network so that no node is isolated. It is a fundamental model for local coverage in network design. Formally, given a graph with non-negative costs , the goal is to find a minimum cost subset of edges such that every vertex is incident to at least one edge of . Its natural generalization, denoted -Edge-Cover, requires a minimum cost subset of edges such that every vertex is incident to at least edges in . Both problems are solvable in polynomial time via reductions to maximum weight matching and maximum weight -matching, respectively [32].
Motivated by the varying reliability of network components, a substantial body of work on network design has developed and studied non-uniform failure models, including flexible network design, bulk-robust network design, and relative survivable network design [2, 18, 23]. The same considerations arise for local coverage. For example, protected wired links may remain operational while wireless links could be disrupted by radio interference. Preserving the required number of operational links at every site creates a tradeoff between investing in protected connections and providing additional redundancy for vulnerable ones.
We introduce Flex-Edge-Cover to capture this tradeoff. The input is an undirected graph , whose edges are partitioned into safe edges and unsafe edges , non-negative edge costs , and non-negative integers . For a vertex and a set of edges, we write to denote the edges of incident to vertex and say that is safe-covered by if , is cumulative-covered by if , and is -Flex-Covered by if is either safe-covered or cumulative-covered by . The goal is to find a minimum cost subset such that every is -Flex-Covered, i.e., satisfies
Equivalently, we are seeking a minimum-cost subset of edges such that remains a -edge-cover after the failure of any set of at most unsafe edges. We allow parallel edges unless otherwise stated.
Our motivation for Flex-Edge-Cover also comes from the flexible edge connectivity problem, denoted -FGC, which requires a minimum cost subgraph that remains -edge-connected after the failure of any set of at most unsafe edges. Introduced for by Adjiashvili, Hommelsheim, and Mühlen-thaler [1] and generalized by Boyd, Cheriyan, Haddadan, and Ibrahimpur [16], this problem equivalently imposes the same alternative as (1) on every non-empty proper cut: at least safe edges or at least total edges should cross every non-empty proper cut. Thus, Flex-Edge-Cover is a relaxation of -FGC since it imposes requirements only across singleton cuts. Several recent works including that of Chekuri-Jain [18] and Ibrahimpur-Végh [26] developed LP-formulations for -FGC via combinatorial arguments. Despite substantial progress on this problem [8, 7, 9, 16, 18], including an -approximation [26] and a very recent -approximation [17], a universal constant factor approximation independent of and remains open. Our interests in Flex-Edge-Cover originated from here. Flex-Edge-Cover localizes the disjunctive requirements to individual vertices, providing a setting in which to develop relaxations and rounding methods that might generalize to the more general -FGC.
From an integer programming perspective, Flex-Edge-Cover is a covering problem with an explicit disjunction at each vertex. Optimizing at each vertex in isolation is easy: choose the cheaper of its cheapest safe incident edges and its cheapest incident edges. Taking the union of these local choices gives a 2-approximation. Improving on this bound requires exploiting the fact that an edge serves both end-vertices. A natural LP with a fractional variable selecting each vertex’s alternative has unbounded integrality gap—see § 5.1. We observe that the disjunctive constraint structure at each vertex lends itself to the use of disjunctive programming principles developed by Balas. We use Balas’ ideas to formulate a stronger LP by convexifying each local feasible set exactly and coupling these convex hulls through shared edge variables. We design a rounding algorithm relative to this stronger LP to improve on the 2-approximation for simple graphs. We complement our approximation results by showing that the problem is APX-hard on simple bipartite graphs.
Our disjunctive programming approach also extends to -FGC leading to a new LP-relaxation. We show that this relaxation is at least as strong as those of Chekuri-Jain [18] and Ibrahimpur-Végh [26]. We observe that this relaxation admits an efficient separation oracle and is hence, polynomial-time solvable via the Ellipsoid method. We conjecture that its integrality gap is bounded by a universal constant independent of and . More broadly, our work advances the use of disjunctive programming in approximation algorithms by translating disjunctive constraints into improved LP-relative guarantees, providing a stepping stone toward a constant-factor LP-rounding algorithm for -FGC.
Results
If , then Flex-Edge-Cover is reduces to the polynomial-time solvable -Edge-Cover. However, for general , the problem is APX-hard (even on simple bipartite graphs for and ).
Theorem 1.1. For every , Flex-Edge-Cover is -hard to approximate within a factor of on simple bipartite graphs even for and .
The local 2-approximation described earlier has a tight example—see § 5.2. Our main algorithmic result improves on the 2-factor.
Theorem 1.2. There is a randomized polynomial-time algorithm for Flex-Edge-Cover with approximation factor 1.78 on simple graphs and on simple bipartite graphs, where the approximation guarantees are in expectation and relative to a polynomial-time solvable LP.
The main message of this work is the use of disjunctive programming techniques in approximation algorithms: exact local convexification via disjunctive programming techniques is strong enough to beat the naive 2-factor for Flex-Edge-Cover. We will elaborate on the LP and the rounding strategy shortly. Our approach leads to a new LP-relaxation for -FGC—we discuss this in § 4. We hope that the rounding algorithm for the disjunctive programming based LP for Flex-Edge-Cover could serve as a stepping stone towards a constant factor approximation for -FGC via our new LP-relaxation.
Discussion on Disjunctive Programming. Disjunctive programming, developed by Balas in the 1970s, provides a systematic framework for exploiting disjunctive alternatives in integer programming. Its convexification principle yields extended formulations for the convex hulls of finite unions of polytopes [5], providing a general tool for constructing strong LP relaxations. The convexification principle also underlies split cuts, an important family of cutting planes in integer programming. Split cuts are derived from the alternatives or for integral vector and integer scalar . The split closure intersects the convex hulls obtained from all such splits and is a rational polyhedron if the original polyhedron is rational [22]. Split cuts are close counterparts of Chvátal-Gomory (CG) cuts, and have a rich theory comparing closure strength and rank (e.g., see [20, 10]).
Disjunctive programming has found numerous applications in combinatorial optimization [28, 14, 34, 21, 4, 15, 25, 11, 12, 29, 13, 24]. To the best of authors’ knowledge, there are only a handful of applications of disjunctive programming in approximation algorithms. Bienstock [11] and Bienstock–McClosky [12] used disjunctions to construct approximate extended LP formulations for knapsack and certain fixed-charge flow sets. Pritchard [29] extended this approach to fixed-dimensional knapsack. Bienstock, Sethuraman, and Ye [13] combined disjunctive formulations with rounding to obtain approximation algorithms for incremental knapsack. Faenza and Malinović [24] rounded a disjunctive programming-based LP to design a PTAS for time-invariant incremental knapsack. Our work adds to this relatively short known list of applications of disjunctive programming in approximation algorithms.
Extensions. Our techniques can be generalized to obtain a tighter 1.73-approximation even in multigraphs. This involves strengthening the LP further using configuration variables. The strengthening complicates the presentation and we avoid these details in the interests of illustrating the main message of the work—namely, disjunctive programming is a concrete approach to design approximation algorithms for flexible network design.
Techniques and AI Disclosure
The hardness result is via reduction from vertex cover in cubic graphs. We describe the techniques for our approximation result henceforth. We first describe the natural LP-relaxation and the need to strengthen it. Let be an undirected graph whose edges are partitioned into safe edges and unsafe edges . We write and for a vector and an edge set , let . Introducing an edge variable for each to indicate whether the edge is chosen and a vertex variable for each to indicate whether the vertex is safe-covered gives the following LP-relaxation:
While is natural, its integrality gap is unbounded—see § 5.1 for an unbounded integrality gap instance.
We use techniques from disjunctive programming to formulate a tighter LP-relaxation now. For each , we define discrete sets
The convex hulls of both and are integral polytopes that admit a polyhedral description: namely the box constraints and the lower bound constraint. Applying Balas’ formulation to the union of these two convex hulls gives our LP-relaxation. Concretely, in addition to edge and vertex indicator variables as above, we introduce two edge-variable vectors for each vertex , and consider the following LP-relaxation:
The formulation has variables and constraints and is hence solvable in polynomial time. We first show that is indeed a relaxation of Flex-Edge-Cover.
Proposition 1.3. Let be a feasible Flex-Edge-Cover on instance . Then, there exist , , for each such that is feasible to , where is the indicator vector of .
Proof. For each , we set if and otherwise. For each , we set
The resulting point satisfies the constraints of .
The projection of to -variables is exactly the set of vectors whose restriction to belongs to for every . We formalize this now. For a vector and a vertex , we denote the restriction of the vector to the variables corresponding to by .
Lemma 1.4. Given a point that is feasible for , for each vertex ,
(1) there exist , such that and
(2) the vector is a convex combination of vectors in and such a convex combination can be computed in polynomial time.
Proof. By the constraints, we have that , where and . If , then taking and gives the needed conclusion. If , then take and and if , then take and to obtain the desired conclusion. Thus, we have , such that . We observe that are computable in polynomial time.
Next, we observe that and is an integral polytope whose extreme points are vectors in . Thus, by Caratheodary’s theorem, is a convex combination of vectors in and such a convex combination can be computed in polynomial time (see [31]). Similarly, is a convex combination of vectors in and such a convex combination can be computed in polynomial time. Finally, we note that is a convex combination of and and thus, is a convex combination of vectors in and such a convex combination can be computed in polynomial time.
Rounding. We interpret the decomposition of in Lemma 1.4(2) as a local distribution over feasible local edge sets with edge marginals . In the first phase, we choose a set of vertices suitably—the precise way to choose will be described shortly. Next, we independently sample a local cover at each vertex of according to the local distribution. Their union -flexible covers every vertex in and let the union be denoted as . In the second phase, we address the coverage of remaining vertices. For each remaining vertex, we add a cheapest set of incident edges to to achieve either safe coverage or cumulative coverage—this is easy to compute via greedy. The non-trivial issue is bounding the augmentation cost in the second phase by exploiting the coverage already supplied by the sampled local covers for vertices in . We next explain how to pick the set and the analysis.
We first focus on simple bipartite graphs since the choice of and the analysis are easier to describe. Our ideas for general graphs originated by considering bipartite graphs. Here, we choose to be one side of the bipartition. Then, the expected sampling cost in the first phase is exactly . At each vertex on the other side, distinct incident edges are supplied by distinct independently sampled neighbors owing to simplicity of the graph. This independence allows us to bound the expected augmentation cost in the second phase at each remaining vertex by at most (this is the non-trivial part of the argument). Thus, the total expected cost is times the cost of the LP.
For general simple graphs (that may not be bipartite), we include each vertex into independently with probability . Then, the expected sampling cost is at most . Conditional on a vertex lying outside , its incident edge is independently chosen in the first phase set with probability ; we use this fact to show that the expected augmentation cost in the second phase at each remaining vertex is at most . Thus, the total expected cost is leading to an approximation factor of
Choosing makes this expression to be about 1.78. Again, simplicity is used precisely to obtain independence among the contributions to an unsampled vertex; parallel edges can be supplied by the same neighbor leading to correlated inclusions and we avoid this via the simplicity assumption.
AI Disclosure. ChatGPT 5.5 was used to prove the moment bound in Lemma 3.4 and it suggested reducing from minimum cardinality vertex cover in simple cubic graphs to obtain the hardness result stated in Theorem 1.1. ChatGPT 6.1 Sol was used to obtain the unbounded integrality gap instance for stated in § 5.1 and ChatGPT Astra was used to assist with literature survey and the writing of the introduction.
Related Work. Several variants of edge cover have been investigated and we mention a few. Vertex-specific degree requirements instead of uniform requirements as in -Edge-Cover remains tractable through -matching [32]. In Colorful Edge Cover problem, vertices are colored and the goal is to cover at least vertices of color for each color using a minimum sized set of edges and this problem is also tractable [6]. Activation Edge Cover aims to minimize vertex payments to activate edges—it is NP-hard and has been studied from the perspective of approximation [27]. An especially relevant variant to our work is the demand edge cover problem introduced by Pritchard and Chakrabarty [30]. In this problem, each edge has a value and each vertex has a demand and the goal is to find a minimum cost subset of edges such that the sum of the values of edges incident to the vertex meets the demand of the vertex for all vertices. They prove that it is impossible to obtain a -approximation for this problem for every constant . It is possible to show APX-hardness of Flex-Edge-Cover by reducing from demand edge cover but the resulting instances are multigraph instances and not simple. The reduction that we present shows APX-hardness for simple graphs.
Hardnesss and Inapproximability
We show APX-hardness of Flex-Edge-Cover on simple bipartite graphs in this section. We reduce Vertex-Cover in cubic graphs to Flex-Edge-Cover to prove Theorem 1.1. In Vertex-Cover, the input is a graph and the goal is to find a minimum cardinality subset of vertices such that every edge has at least one endpoint in . Chlebík and Chlebíková [19] showed that Vertex-Cover in simple cubic graphs is NP-hard to approximate within a factor of for every .
Proof of Theorem 1.1. We reduce minimum cardinality vertex cover in simple cubic graphs to Flex-Edge-Cover. Let be an instance of minimum cardinality vertex cover. We set and , construct a graph and cost function as follows. The set consists of 3 copies of each vertex and 5 vertices for each edge . The set consists of safe edges with for each , safe edges with for each , unsafe edges and with for each , unsafe edges with for each and , safe edges with for each and . We note that the constructed graph is simple bipartite with bipartition and . See Figure 1 for an illustration of . Let be the value of the smallest vertex cover in and be the optimal value of Flex-Edge-Cover on .

Figure 1. An illustration of the construction of . Continuous edges are safe and dashed edges are unsafe. Edge labels refer to the costs. The shaded parts and the unshaded parts show a bipartition of .
Let be a vertex cover of . We construct a subset as follows. For every vertex , add the three unsafe edges of the form to . For every vertex add the safe edges and to . Lastly add the edges and for all , . We observe that is feasible for Flex-Edge-Cover on instance . We have that , and hence, .
Next, let be a feasible solution to the Flex-Edge-Cover instance . Let . We show that is a vertex cover in . Fix an edge . Since the vertex is incident to 4 edges, which are all unsafe, we must have that by definition of . Since 2 of the edges incident to are of the form , by the pigeonhole principle, contains an edge for some vertex . Since covers and , is a vertex cover. Next, we bound the size of the vertex cover . If , then edge of cost 2 is in and so . Otherwise, suppose . This implies that for some . If , then . Otherwise and so must contain the three edges of the form , which again implies . Thus, we conclude that
Therefore, we have that . Since we showed earlier that the reverse inequality holds, we have that
For all simple graphs , we have that . This follows since given any vertex cover of , we have that . If is a cubic graph we have that . Thus, for all cubic graphs . Suppose we had a -approximation to Flex-Edge-Cover on instance that returned a solution . From the previous analysis, is a vertex cover in . We have that
where (4) follows from (2), (5) follows from (3), and (6) follows from the fact that is cubic. Thus, a -approximation for Flex-Edge-Cover would give a approximation to minimum cardinality vertex cover on cubic graphs. This implies that a approximation for Flex-Edge-Cover would yield a approximation for Vertex-Cover, which is NP-hard via the results of Chlebík and Chlebíková [19].
Approximation Algorithms
In this section, we design approximation algorithms for Flex-Edge-Cover in simple graphs to prove Theorem 1.2. Our algorithm starts with an optimum solution to and will round it. The rounding algorithm additionally takes a subset as input whose significance will be clear shortly. The rounding algorithm proceeds in two phases. The algorithm addresses the covering requirements of vertices in in the first phase as follows: let . By Lemma 1.4, is a convex combination of safe-satisfying vectors and cumulative-satisfying vectors (i.e., vectors in and ). The algorithm samples a vector among all vectors in the convex combination with probability proportional to its coefficient in the convex combination. It sets the solution of the first phase as . We observe that each is either safe-covered or cumulative-covered by and hence, by and moreover, the expected cost of is at most the cost of the LP solution (since is an independent set and consequently for every ). However, we could have vertices that are uncovered by (i.e., neither cumulative-covered nor safe-covered). The algorithm addresses the covering-requirements for vertices in in the second phase as follows: for each , it computes a cheapest augmentation set to that makes safe-covered (by greedy), a cheapest augmentation set to that makes cumulative-covered (by greedy), and sets . It sets the solution of the second phase as and returns . See Algorithm 1 for a formal description.
Essentially, the algorithm uses the LP solution to sample and satisfy the covering requirements for vertices in in the first phase and in the second phase, it augments the solution from the first phase with additional edges to meet the covering requirements for each vertex in . If , then the algorithm does not take advantage of the LP solution and simply corresponds to the naive greedy algorithm mentioned in the introduction which yields a 2-approximation which is also the best possible. Our key contribution is an LP-informed greedy augmentation that improves on the 2-factor. Our choice for varies between bipartite graphs and non-bipartite graphs and we will discuss it shortly.
We first show that Algorithm 1 can be implemented to run in polynomial time and argue its correctness.
Lemma 3.1. Algorithm 1 can be implemented to run in polynomial time.
Algorithm 1 Rounding Algorithm
1: Input: $G = (V, E = S \cup U)$, $c : E \to \mathbb{R}_{\ge 0}$, $p,q$, Feasible solution $(x,\alpha,\beta,\lambda)$ to $(LP_2)$, a subset $L \subseteq V$.
2: for each $v \in L$ do
3: Express $x_{\delta(v)}$ as a convex combination of vectors in $\mathcal{A}_v \cup \mathcal{B}_v$, say $x_{\delta(v)} = \sum_{a\in\mathcal{A}_v\cup\mathcal{B}_v}\lambda_a a$ with $\sum_{a\in\mathcal{A}_v\cup\mathcal{B}_v}\lambda_a = 1$ and $\lambda_a \ge 0$ for all $a \in \mathcal{A}_v \cup \mathcal{B}_v$
4: Sample $a \in \mathcal{A}_v \cup \mathcal{B}_v$ with probability proportional to $\lambda_a$ and set $F_v = \operatorname{support}(a)$
5: end for
6: $F_1 \leftarrow \bigcup_{v\in L}F_v$
7: for each $u \in V \setminus L$ do
8: $A_u^1 \leftarrow \arg\min \{c(A) : A \subseteq \delta_S(u) \setminus F_1,\ \lvert(\delta(F_1\cup A)\cap S(u))\rvert \ge p\}$
9: $A_u^2 \leftarrow \arg\min \{c(A) : A \subseteq \delta(u) \setminus F_1,\ \lvert\delta_{F_1\cup A}(u)\rvert \ge p+q\}$
10: $A_u \leftarrow \arg\min\{c(A_u^1),c(A_u^2)\}$
11: end for
12: $F_2 \leftarrow \bigcup_{u\in V\setminus L}A_u$
13: return $F := F_1 \cup F_2$
Proof. Step 3 can be implemented in polynomial time via Lemma 1.4; we note that the convex combination has at most polynomially many non-zero coefficients. Consequently, the sampling procedure in Step 4 is also implementable in polynomial time. Steps 8 and 9 are greedy procedures that can be implemented in polynomial time via a sorting algorithm. Thus, the entire algorithm can be implemented in polynomial time. Next, we show that the algorithm returns a feasible solution.
We now prove correctness of the algorithm.
Lemma 3.2. For every choice of , Algorithm 1 returns a feasible flexible-edge-cover for the instance .
Proof. Let be the solution returned by the algorithm for the input instance with a feasible solution to . We show that every vertex is either safe-covered or cumulative-covered by .
Let . We recall that with and for all . For each , we have that is safe-covered by and for each , we have that is cumulative-covered by . Thus, for each , we have that is either safe-covered or cumulative-covered by . Hence, is either safe-covered or cumulative-covered by .
Next, consider . We have two cases: (i) Suppose . We recall that
and hence, . Consequently, is safe-satisfied by . (ii) Suppose . We recall that
and hence, . Consequently, is cumulative-satisfied by .
The rest of the section is devoted to analyzing the approximation factor via a careful choice of in bipartite and non-bipartite graphs. All graphs in the remainder of this section are simple. To analyze the approximation factor, we address the expected cost of the solution from the two phases. In the first phase, our sampling strategy depends on the LP solution which allows us to show that the cost of is small relative to the LP. In the second step, we augment with additional edges in a greedy manner to fix the covering requirements of vertices in . This augmentation step incurs additional cost that is non-trivial to bound. In Section 3.1, we prove a key technical lemma that helps bound the cost incurred in an augmentation step in a general setting. In Section 3.2, we adapt this technical lemma to the context of Flex-Edge-Cover to bound the cost incurred by the augmentation step relative to the objective value of . In Section 3.3, we specify the choice of and design a 1.606-approximation for simple bipartite graphs. In Section 3.4, we specify the choice of and design a 1.78-approximation for simple non-bipartite graphs. The rounding strategy for bipartite graphs is slightly simpler and its analysis served as the starting point of our rounding strategy for non-bipartite graphs, so we encourage readers to read Section 3.3 on bipartite graphs as a precursor to reading Section 3.4 for non-bipartite graphs. For a real value , we use the convention that .
Key Technical Lemma
In this section, we show the following key technical lemma that compares the cost of the cheapest -element subset to the cost of the cheapest augmentation to a randomly sampled subset to achieve .
Lemma 3.3. Let be a ground set with cost function and be a positive integer. Let , i.e., is the sum of the costs of the cheapest elements of . Let and such that for all and . Let be a random set obtained by selecting each element with probability independently. Then,
We need the following helper lemma to prove Lemma 3.3.
Lemma 3.4. Let be independent Bernoulli variables with , , and . For every non-negative integer , we have that
Proof. Let . We have that by convexity of the function given by . Thus, we have that . Hence,
where (7) is by independence of , (8) is because takes values in for every , and (9) is by convexity of the function .
We now prove Lemma 3.3.
Proof of Lemma 3.3. For a real value , we define and . For a positive integer and a real value , we define . For a subset and a positive integer , we define . We define . For a set , we denote the real-valued function as if and if .
We need to show that . Let us fix a set and consider . We can express as . Swapping the order of the finite sum and the integral gives
We will use the following claim to simplify for a fixed .
Claim 3.5. Let . Then, .
Proof. We note that counts exactly the elements in that have cost at least . Since , . We first show that by considering two cases:
Case (i). . Since is a subset of that contains the cheapest items of , contains all the items in and hence contains the cheapest items of . Thus, in this case there are exactly elements in that have cost at least .
Case (ii). . In this case, does not contain elements with cost at least . Thus has exactly with cost at least .
Now, we have that
where (10) follows from the fact that .
By Claim 3.5, we have that
We note that , which implies that
Hence, we have that
Let us fix and consider . Lemma 3.4 implies that for , . If , then trivially . Thus, we have that
where (11) follows from the hypothesis that for all and (12) follows from the fact that for . We now bound . Without loss of generality, let the items be ordered such that and let . For , we have that . Thus,
Thus, .
Augmentation Cost
We now use Lemma 3.3 to bound the augmentation cost of covering a vertex after sampling the edges incident to it according to a distribution that depends on .
Lemma 3.6. Let be the input instance of Flex-Edge-Cover, be a feasible solution to . Let and . Let denote the set of edges obtained by sampling each edge independently with probability . Let
Then,
Proof of Lemma 3.6. We define
By the first part of Lemma 1.4, we have that where and . Thus, and and moreover, and . Applying Lemma 3.3 to with cost function , , , , we obtain that
Applying Lemma 3.3 to with cost function , , , , we obtain that
Consequently, we have that
where inequality (13) is because the minimum of a collection of non-negative numbers is at most the geometric mean, inequality (14) is because the geometric mean is at most the arithmetic mean, inequality (15) is because and for all , inequality (16) is because and , and inequality (17) is because .
Bipartite Graphs
Suppose the input graph is is bipartite. We pick to be one part of a valid bipartition of and use Algorithm 1. Lemma 3.2 implies that the solution returned by Algorithm 1 is indeed a feasible solution. We now analyze the approximation factor.
Lemma 3.7. Let be a bipartite input instance of Flex-Edge-Cover. Let be the solution returned by Algorithm 1 implemented with being one part of a valid bipartition of . Then,
Proof. We observe that and hence, . We bound the expected cost of and separately. First, we bound . We have that
The first and third equalities are owing to the bipartiteness of . The second equality is because for each , for each edge , the probability of sampling into is exactly .
Next, we bound . Let . For each , the edge is sampled into independently with probability ; independence holds because is a simple graph and the probability of sampling into depends only on the distribution at the other end-vertex of . Independence allows us to apply Lemma 3.6. Hence, applying Lemma 3.6 with , we have that
Hence,
Again, the first and third equalities are owing to the bipartiteness of . Consequently, .
Remark 3.8. We note that this algorithm cannot be de-randomized in the natural way; the natural procedure is for each vertex , compute a subset that has the cheapest edges incident to and for each vertex , compute the subset . In the worst case, this procedure has an approximation factor asymptotically approaching two (see § 5.2).
Non-Bipartite Graphs
The choice of for bipartite graphs informs our rounding strategy for non-bipartite graphs. For bipartite graphs, we had the bipartition and of vertices and our algorithm proceeded in two phases: we used the LP solution to sample and satisfy the covering requirements for vertices in in the first phase and in the second phase, we augmented the solution from the first phase with additional edges to meet the covering requirements for vertices in . For non-bipartite graphs, it is unclear how to pick the subset so that we can employ the same two-phase strategy. Two natural boundary cases are worth mentioning here: (i) if we choose to use the LP-solution to meet the covering requirements of vertices in in the first phase and augment to meet the covering requirements of vertices in in the second phase, then the resulting algorithm is simply the naive greedy algorithm described in the introduction which results in a 2-factor which is also the best possible. (ii) if we choose to use the LP-solution to meet the covering requirements of vertices in in the first phase and augment to meet the covering requirements of vertices in in the second phase, then the resulting algorithm again achieves a 2-factor (we were able to show this by adapting the analysis for bipartite graphs).
For non-bipartite graphs, instead of deterministically deciding on , we randomly sample each vertex into the first phase set with probability (where the value of will be chosen later). For , we run Algorithm 1 for such a random choice of . We now show that this rounding strategy achieves an approximation ratio of 1.78.
Lemma 3.9. Let be the solution returned by Algorithm 1 implemented for a random set , where is obtained by picking each vertex into with probability . Then,
:::`
Proof. We observe that and hence, . We bound the expected cost of and separately. First, we bound . We have that
The second equality is because each is sampled into with probability . The third equality is because for each , for each edge , the probability of sampling into is exactly . The final equality is because the term for each is counted from the perspective of both end-vertices of .
Next, we bound . We note that
Let . We have that . We now focus on . Condition on the event that . For each , the edge is sampled into independently with probability : This is because, the edge is present in only if the other end-vertex of is chosen into and conditioned on , we have that is sampled into with probability . The probability of being sampled into is and conditioned on , the probability of is (since is simple); thus, the probability of is . Moreover, independence holds because is a simple graph. Independence allows us to apply Lemma 3.6. Hence, applying Lemma 3.6 with , we have that
Hence,
The second inequality is because each is in with probability $1-\theta$. The final equality is because the term for each is counted from the perspective of both end-vertices of $e.
Consequently, we have that
For , we have that , thus bounding the approximation factor. Our choice of is because the minimum value of the expression over occurs at with (since is convex).
Flexible Graph Connectivity via Disjunctive Programming
In this section, we formulate a new LP-relaxation based on disjunctive programming for the flexible graph connectivity problem. This LP-relaxation is stronger than known relaxations given by Chekuri-Jain and Ibrahimpur-Vegh [18, 26] and is also polynomial-time solvable. We recall the definition of Flex-Graph-Connectivity.
Definition 4.1. In Flex-Graph-Connectivity, the input is a graph , positive integers and , and a cost function . Here, the sets and are denoted as safe and unsafe edges, respectively. The goal is to find a subset with the least cost such that for every subset , has at least safe edges crossing the cut or edges crossing the cut .
This project started by examining Ibrahimpur-Vegh’s LP relaxation for Flex-Graph-Connectivity. We noticed that their LP is not integral for the special case where has only two vertices. This special case is a disjunctive variant of the Minimum-Cost-Unit-Weight-Knapsack problem, denoted Disjunctive-Knapsack-Cover: the input is a ground set , cost function , and positive integers and . The goal is to select a subset of minimum cost s.t. or . Disjunctive-Knapsack-Cover can be solved in polynomial time as follows: Let be the cheapest elements of and be the cheapest elements of . Output . Our initial goal for a stronger LP for Flex-Graph-Connectivity was to obtain an integral LP for this special case. We used the disjunctive programming approach to obtain such an LP. Extending this approach to arbitrary graphs, leads to the following LP-relaxation for Flex-Graph-Connectivity.
By eliminating and variables via Fourier-Motzkin elimination in a suitable order, we obtain the following LP that is equivalent to —we do not show the Fourier-Motzkin derivation in the interests of brevity.
Next, we eliminate the variables from to arrive at the following LP:
We briefly outline why and are equivalent. If we have a feasible solution for , then the solution obtained by setting for each , where
is feasible for . Moreover, if is a feasible solution for , then can be shown to satisfy the constraints of by a straightforward derivation. We do not elaborate on these details since these LPs are not the main focus of this work.
Solvability of the LP. We note that can be solved in polynomial time via the Ellipsoid method since it admits a polynomial time separation oracle (even if and are part of input and not fixed constants). For each family of constraints, the separation problem can be reduced to cardinality-constrained global min-cut interdiction. Zenklusen [33] showed that cardinality-constrained global min-cut interdiction can be solved in polynomial time via reduction to 2-criteria global minimum cut which, in turn, is known to be polynomial-time solvable [3].
Strength of the LP compared to known LPs. dominates the relaxation of Ibrahimpur-Végh [26], which in turn dominates that of Chekuri-Jain [18]. The first dominance can be strict, even on simple graphs. Indeed, the first family of constraints in , together with the second family restricted to , recovers the Chekuri–Jain relaxation. The full second family strengthens the corresponding Ibrahimpur-Végh inequalities, while the remaining inequalities of their relaxation follow from the first family and the box constraints. Beyond this strengthening, the disjunctive formulation exposes local convex decompositions that underpin our rounding algorithms for Flex-Edge-Cover. These results suggest that exploiting the same structure across general cuts is a promising route toward a constant-factor algorithm for Flex-Graph-Connectivity.
Appendix
Integrality Gap of (LP1)
We show that has unbounded integrality gap.
Proposition 5.1. has unbounded integrality gap on simple bipartite graphs.
Proof. We construct a simple bipartite instance to exhibit an unbounded integrality gap. Let and be the complete bipartite graph on vertices on both sides. Let the bipartition be . We assign the edges in to and as follows. Decompose into edge disjoint perfect matchings (this is possible because is a complete bipartite graph with equal number of vertices on both sides). Let and .
Define the cost function as
Let be an optimal integral solution to this instance of Flex-Edge-Cover. Since and , must include the edge . Hence, .
We now construct a feasible solution to . Let for all vertices and let
Then, and . For every vertex
Thus is feasible for and the integrality gap is at least
which tends to as .
Tight example for the naive greedy heuristic
In this section, we investigate the naive greedy heuristic stated in the introduction: namely, for each vertex , let be the cheapest edges incident to , be the cheapest safe edges incident to , and ; return . We construct an instance to illustrate that 2-factor is the best possible for this heuristic.
Let and . We construct a graph where , , . Define a cost function where for every and for every . For sufficiently small, the optimal solution is with . We can adversarially set the processing order of the vertices to be first and then . Then, the algorithm will construct the solution . We have that
As and , this ratio approaches 2. We note that this example is a simple graph.
References
- [1]D. Adjiashvili, F. Hommelsheim, and M. Mühlenthaler. Flexible graph connectivity. Mathematical Programming, 192:409–441, 2022.
- [2]D. Adjiashvili, S. Stiller, and R. Zenklusen. Bulk-robust combinatorial optimization. Mathematical Programming, 149(1-2):361–390, 2015.DOI
- [3]A. Armon and U. Zwick. Multicriterial global minimum cuts. Algorithmica, 46(1):15–26, 2006.
- [4]A. Atamtürk. Strong formulations of robust mixed 0–1 programming. Mathematical Programming, 108(2):235–250, 2006.DOI
- [5]E. Balas. Disjunctive programming. Annals of Discrete Mathematics, 5:3–51, 1979.
- [6]S. Bandyapadhyay, A. Banik, and S. Bhore. On colorful vertex and edge cover problems. Algorithmica, 85(12):3816–3827, 2023.arxiv.org/abs/2308.15842
- [7]I. Bansal. A global analysis of the primal-dual method for edge augmentation problems. In Integer Programming and Combinatorial Optimization, 2025.DOI
- [8]I. Bansal, J. Cheriyan, L. Grout, and S. Ibrahimpur. Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions. Algorithmica, 86(8):2575–2604, 2024.
- [9]I. Bansal, J. Cheriyan, S. Khanna, and M. Simmons. Improved Approximation Algorithms for Capacitated Network Design and Flexible Graph Connectivity. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP), pages 20:1–20:20, 2025.arxiv.org/abs/2411.18809
- [10]A. Basu, M. Conforti, M. Di Summa, and H. Jiang. Split cuts in the plane. SIAM Journal on Optimization, 31(1):331–347, 2021.arxiv.org/abs/2003.05022
- [11]D. Bienstock. Approximate formulations for 0-1 knapsack sets. Operations Research Letters, 36(3):317–320, 2008.DOI
- [12]D. Bienstock and B. McClosky. Tightening simple mixed-integer sets with guaranteed bounds. Mathematical Programming, 133:337–363, 2012.
- [13]D. Bienstock, J. Sethuraman, and C. Ye. Approximation algorithms for the incremental knapsack problem via disjunctive programming. arXiv preprint arXiv: 1311.4563, 2013.arxiv.org/abs/1311.4563
- [14]D. Bienstock and M. Zuckerberg. Subset algebra lift operators for 0-1 integer programming. SIAM Journal on Optimization, 15(1):63–95, 2004.DOI
- [15]D. Bienstock and M. Zuckerberg. Simpler derivation of bounded pitch inequalities for set covering, and minimum knapsack sets, 2018.arxiv.org/abs/1806.07435
- [16]S. Boyd, J. Cheriyan, A. Haddadan, and S. Ibrahimपुर. Approximation algorithms for flexible graph connectivity. Mathematical Programming, 204:493–516, 2024.
- [17]K. Chandrasekaran, R. Jiang, and K. Kalathur. A (p + q)^{O(pq)}-approximation for (p,q)-flexible graph connectivity. arXiv preprint arXiv:2609.14243, 2026.arxiv.org/abs/2609.14243
- [18]C. Chekuri and R. Jain. Approximation algorithms for network design in non-uniform fault models. Mathematical Programming, Series A, October 2025.
- [19]M. Chlebík and J. Chlebíková. Complexity of approximating bounded variants of optimization problems. Theoretical Computer Science, 354(3):320–338, 2006.DOI
- [20]M. Conforti, A. Del Pia, M. Di Summa, Y. Faenza, and R. Grappe. Reverse Chvátal–Gomory rank. SIAM Journal on Discrete Mathematics, 29(1):166–181, 2015.
- [21]M. Conforti and L. A. Wolsey. Compact formulations as a union of polyhedra. Mathematical Programming, 114(2):277–289, 2008.DOI
- [22]W. Cook, R. Kannan, and A. Schrijver. Chvátal closures for mixed integer programming problems. Mathematical Programming, 47(1-3):155–174, 1990.DOI
- [23]M. Dinitz, A. Koranteng, and G. Kortsarz. Relative survivable network design. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX-RANDOM, pages 41:1–41:29, 2022.arxiv.org/abs/2206.12245
- [24]Y. Faenza and I. Malinovic. A PTAS for the Time-Invariant Incremental Knapsack Problem. In International Symposium on Combinatorial Optimization (ISCO), pages 157–169, 2018.arxiv.org/abs/1701.07299
- [25]S. Fiorini, T. Huynh, and S. Weltge. Strengthening convex relaxations of 0/1-sets using Boolean formulas. Mathematical Programming, 190(1-2):467–482, 2021.
- [26]S. Ibrahimpur and L. Végh. An O(log n)-approximation algorithm for (p,q)-flexible graph connectivity via independent rounding. Mathematical Programming, 2026.
- [27]G. Kortsarz, Z. Nutov, and E. Shalom. Approximating activation edge-cover and facility location problems. Theoretical Computer Science, 930:218–228, 2022.
- [28]A. N. Letchford. On disjunctive cuts for combinatorial optimization. Journal of Combinatorial Optimization, 5(3):299–315, 2001.
- [29]D. Pritchard. An LP with Integrality Gap 1 + ϵ for Multidimensional Knapsack. arXiv preprint arXiv: 1005.3324, 2010.arxiv.org/abs/1005.3324
- [30]D. Pritchard and D. Chakrabarty. Approximability of sparse integer programs. Algorithmica, 61(1):75–93, 2011.
- [31]A. Schrijver. Theory of linear and integer programming. John Wiley & Sons, 1998.
- [32]A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003.
- [33]R. Zenklusen. Connectivity interdiction. Operations Research Letters, 42(6):450–454, 2014.DOI
- [34]M. Zuckerberg. A Set Theoretic Approach to Lifting Procedures for 0,1 Integer Programming. PhD thesis, Columbia University, 2004.