betaFeedback

WorksComputer 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 pp and qq, and the goal is to find a minimum cost subset of edges such that each vertex has either at least pp safe edges incident to it or at least p+qp+q total edges incident to it. We show that FLEX-EDGE-COVER is APX-hard in simple bipartite graphs. A greedy approach leads to a 22-approximation in all graphs. We show that the 22-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 (p,q)(p,q)-FGC) which has garnered much recent attention. For (p,q)(p,q)-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 (p,q)(p,q)-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 G=(V,E)G=(V,E) with non-negative costs c:E→R≥0c:E\to\mathbb{R}_{\ge0}, the goal is to find a minimum cost subset F⊆EF\subseteq E of edges such that every vertex is incident to at least one edge of FF. Its natural generalization, denoted pp-Edge-Cover, requires a minimum cost subset FF of edges such that every vertex is incident to at least pp edges in FF. Both problems are solvable in polynomial time via reductions to maximum weight matching and maximum weight bb-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 G=(V,E=S∪U)G=(V,E=S\mathbin{\cup}U), whose edges are partitioned into safe edges SS and unsafe edges UU, non-negative edge costs c:E→Z≥0c:E\to\mathbb{Z}_{\ge0}, and non-negative integers p,q≥0p,q\ge0. For a vertex v∈Vv\in V and a set FF of edges, we write δF(v)\delta_F(v) to denote the edges of FF incident to vertex v∈Vv \in V and say that vv is safe-covered by FF if ∣δF∩S(v)∣≥p|\delta_F \cap S(v)| \ge p, vv is cumulative-covered by FF if ∣δF(v)∣≥p+q|\delta_F(v)| \ge p+q, and vv is (p,q)(p,q)-Flex-Covered by FF if vv is either safe-covered or cumulative-covered by FF. The goal is to find a minimum cost subset F⊆EF \subseteq E such that every vv is (p,q)(p,q)-Flex-Covered, i.e., FF satisfies

∣δF∩S(v)∣≥por∣δF(v)∣≥p+qfor every v∈V.(1)|\delta_F \cap S(v)| \ge p \qquad\text{or} \qquad|\delta_F(v)| \ge p+q \qquad\text{for every } v \in V. \tag*{(1)}

Equivalently, we are seeking a minimum-cost subset FF of edges such that FF remains a pp-edge-cover after the failure of any set of at most qq unsafe edges. We allow parallel edges unless otherwise stated.

Our motivation for Flex-Edge-Cover also comes from the flexible edge connectivity problem, denoted (p,q)(p,q)-FGC, which requires a minimum cost subgraph that remains pp-edge-connected after the failure of any set of at most qq unsafe edges. Introduced for (p,q)=(1,1)(p,q)=(1,1) 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 pp safe edges or at least p+qp+q total edges should cross every non-empty proper cut. Thus, Flex-Edge-Cover is a relaxation of (p,q)(p,q)-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 (p,q)(p,q)-FGC via combinatorial arguments. Despite substantial progress on this problem [8, 7, 9, 16, 18], including an O(log⁡∣V∣)O(\log|V|)-approximation [26] and a very recent (p+q)O(pq)(p+q)^{O(pq)}-approximation [17], a universal constant factor approximation independent of pp and qq 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 (p,q)(p,q)-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 pp cheapest safe incident edges and its p+qp+q 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 (p,q)(p,q)-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 pp and qq. 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 (p,q)(p,q)-FGC.

Results

If q=0q=0, then Flex-Edge-Cover is reduces to the polynomial-time solvable pp-Edge-Cover. However, for general qq, the problem is APX-hard (even on simple bipartite graphs for p=1p=1 and q=2q=2).

Theorem 1.1. For every ϵ>0\epsilon> 0, Flex-Edge-Cover is NPNP-hard to approximate within a factor of 496495−ϵ\frac{496}{495} - \epsilon on simple bipartite graphs even for p=1p = 1 and q=2q = 2.

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 1+e<1.6071 + \sqrt{e} < 1.607 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 (p,q)(p,q)-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 (p,q)(p,q)-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 πTx≤π0\pi^T x \le\pi_0 or πTx≥π0+1\pi^T x \ge\pi_0 + 1 for integral vector π\pi and integer scalar π0\pi_0. 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 G=(V,E=S⊎U)G=(V,E=S\uplus U) be an undirected graph whose edges are partitioned into safe edges SS and unsafe edges UU. We write δ(v)=δE(v)\delta(v)=\delta_E(v) and for a vector z∈REz\in\mathbb{R}^E and an edge set AA, let z(A):=∑e∈Azez(A):=\sum_{e\in A}z_e. Introducing an edge variable xex_e for each e∈Ee\in E to indicate whether the edge ee is chosen and a vertex variable λv\lambda_v for each v∈Vv\in V to indicate whether the vertex vv is safe-covered gives the following LP-relaxation:

min⁡∑e∈Ecexes.t.x(δS(v))≥pλv∀v∈Vx(δ(v))≥(p+q)(1−λv)∀v∈V0≤λv≤1∀v∈V0≤xe≤1∀e∈E.(2)\begin{aligned} \min\quad&\sum_{e\in E}c_ex_e\\ \text{s.t.}\quad&x(\delta_S(v))\ge p\lambda_v &&\forall v\in V\\ &x(\delta(v))\ge(p+q)(1-\lambda_v) &&\forall v\in V\\ &0\le\lambda_v\le1 &&\forall v\in V\\ &0\le x_e\le1 &&\forall e\in E. \tag*{(2)} \end{aligned}

While (LP1)(LP_1) 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 v∈Vv\in V, we define discrete sets

Av:={α∈{0,1}δ(v):α(δS(v))≥p},\mathcal{A}_v:=\{\alpha\in\{0,1\}^{\delta(v)}:\alpha(\delta_S(v))\ge p\},
Bv:={β∈{0,1}δ(v):β(δ(v))≥p+q}.\mathcal{B}_v:=\{\beta\in\{0,1\}^{\delta(v)}:\beta(\delta(v))\ge p+q\}.

The convex hulls of both Av\mathcal{A}_v and Bv\mathcal{B}_v are integral polytopes that admit a polyhedral description: namely the box constraints [0,1]δ(v)[0,1]^{\delta(v)} 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 αv,βv∈{0,1}δ(v)\alpha^v,\beta^v\in\{0,1\}^{\delta(v)} for each vertex v∈Vv\in V, and consider the following LP-relaxation:

min⁡∑e∈Ecexes.t.xe=αev+βev∀e∈δ(v),v∈Vαv(δS(v))≥λvp∀v∈Vβv(δ(v))≥(1−λv)(p+q)∀v∈V0≤αev≤λv∀e∈δ(v),v∈V0≤βev≤1−λv∀e∈δ(v),v∈V0≤λv≤1∀v∈V(3)\begin{aligned} \min\quad&\sum_{e\in E}c_ex_e\\ \text{s.t.}\quad&x_e=\alpha^v_e+\beta^v_e &&\forall e\in\delta(v),v\in V\\ &\alpha^v(\delta_S(v))\ge\lambda_vp &&\forall v\in V\\ &\beta^v(\delta(v))\ge(1-\lambda_v)(p+q) &&\forall v\in V\\ &0\le\alpha^v_e\le\lambda_v &&\forall e\in\delta(v),v\in V\\ &0\le\beta^v_e\le1-\lambda_v &&\forall e\in\delta(v),v\in V\\ &0\le\lambda_v\le1 &&\forall v\in V \tag*{(3)} \end{aligned}

The formulation has O(∣V∣+∣E∣)O(|V|+|E|) variables and constraints and is hence solvable in polynomial time. We first show that (LP2)(LP_2) is indeed a relaxation of Flex-Edge-Cover.

Proposition 1.3. Let F⊆EF\subseteq E be a feasible Flex-Edge-Cover on instance (G=(V,E=S⊎U),p,q)(G=(V,E=S\uplus U),p,q). Then, there exist λ∈{0,1}V\lambda\in\{0,1\}^V, αv∈{0,1}δ(v)\alpha^v\in\{0,1\}^{\delta(v)}, βv∈{0,1}δ(v)\beta^v\in\{0,1\}^{\delta(v)} for each v∈Vv\in V such that (χF,α,β,λ)(\chi^F,\alpha,\beta,\lambda) is feasible to (LP2)(LP_2), where χF∈{0,1}E\chi^F\in\{0,1\}^E is the indicator vector of FF.

Proof. For each v∈Vv\in V, we set λv=1\lambda_v=1 if ∣δS(v)∩F∣≥p|\delta_S(v)\cap F|\ge p and λv=0\lambda_v=0 otherwise. For each v∈V,e∈δ(v)v\in V,e\in\delta(v), we set

αev:={1if e∈F and ∣δS(v)∩F∣≥p,0otherwise,\alpha^v_e:= \begin{cases} 1 & \text{if }e\in F\text{ and }|\delta_S(v)\cap F|\ge p,\\ 0 & \text{otherwise,} \end{cases}
βev:={1if e∈F and ∣δS(v)∩F∣<p,0otherwise.\beta^v_e:= \begin{cases} 1 & \text{if }e\in F\text{ and }|\delta_S(v)\cap F|<p,\\ 0 & \text{otherwise.} \end{cases}

The resulting point (χF,α,β,λ)(\chi^{F},\alpha,\beta,\lambda) satisfies the constraints of (LP2)(LP_2).

The projection of (LP2)(LP_2) to xx-variables is exactly the set xx of vectors whose restriction to δ(v)\delta(v) belongs to conv⁡(Av∪Bv)\operatorname{conv}(\mathcal{A}_v\cup\mathcal{B}_v) for every v∈Vv\in V. We formalize this now. For a vector x∈REx\in\mathbb{R}^{E} and a vertex v∈Vv\in V, we denote the restriction of the vector xx to the variables corresponding to δ(v)\delta(v) by xδ(v)x_{\delta(v)}.

Lemma 1.4. Given a point (x,α,β,λ)(x,\alpha,\beta,\lambda) that is feasible for (LP2)(LP_2), for each vertex v∈Vv\in V,

(1) there exist av∈conv⁡(Av)a^v\in\operatorname{conv}(\mathcal{A}_v), bv∈conv⁡(Bv)b^v\in\operatorname{conv}(\mathcal{B}_v) such that xδ(v)=λvav+(1−λv)bvx_{\delta(v)}=\lambda_v a^v+(1-\lambda_v)b^v and

(2) the vector xδ(v)x_{\delta(v)} is a convex combination of vectors in Av∪Bv\mathcal{A}_v\cup\mathcal{B}_v and such a convex combination can be computed in polynomial time.

Proof. By the constraints, we have that xδ(v)=αv+βvx_{\delta(v)}=\alpha^v+\beta^v, where αv∈λvconv⁡(Av)\alpha^v\in\lambda_v\operatorname{conv}(\mathcal{A}_v) and βv∈(1−λv)conv⁡(Bv)\beta^v\in(1-\lambda_v)\operatorname{conv}(\mathcal{B}_v). If λv∈(0,1)\lambda_v\in(0,1), then taking av=αv/λva^v=\alpha^v/\lambda_v and bv=βv/(1−λv)b^v=\beta^v/(1-\lambda_v) gives the needed conclusion. If λv=0\lambda_v=0, then take av=0a^v=0 and bv=βvb^v=\beta^v and if λv=1\lambda_v=1, then take av=αva^v=\alpha^v and bv=0b^v=0 to obtain the desired conclusion. Thus, we have av∈conv⁡(Av)a^v\in\operatorname{conv}(\mathcal{A}_v), bv∈conv⁡(Bv)b^v\in\operatorname{conv}(\mathcal{B}_v) such that xδ(v)=λvav+(1−λv)bvx_{\delta(v)}=\lambda_v a^v+(1-\lambda_v)b^v. We observe that av,bva^v,b^v are computable in polynomial time.

Next, we observe that av∈conv⁡(Av)a^v\in\operatorname{conv}(\mathcal{A}_v) and conv⁡(Av)\operatorname{conv}(\mathcal{A}_v) is an integral polytope whose extreme points are vectors in Av\mathcal{A}_v. Thus, by Caratheodary’s theorem, ava^v is a convex combination of vectors in Av\mathcal{A}_v and such a convex combination can be computed in polynomial time (see [31]). Similarly, bvb^v is a convex combination of vectors in Bv\mathcal{B}_v and such a convex combination can be computed in polynomial time. Finally, we note that xx is a convex combination of ava^v and bvb^v and thus, xx is a convex combination of vectors in Av∪Bv\mathcal{A}_v\cup\mathcal{B}_v and such a convex combination can be computed in polynomial time.

Rounding. We interpret the decomposition of xδ(v)x_{\delta(v)} in Lemma 1.4(2) as a local distribution over feasible local edge sets with edge marginals xex_e. In the first phase, we choose a set LL of vertices suitably—the precise way to choose LL will be described shortly. Next, we independently sample a local cover at each vertex of LL according to the local distribution. Their union (p,q)(p,q)-flexible covers every vertex in LL and let the union be denoted as FF. In the second phase, we address the coverage of remaining vertices. For each remaining vertex, we add a cheapest set of incident edges to FF 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 LL. We next explain how to pick the set LL and the analysis.

We first focus on simple bipartite graphs since the choice of LL and the analysis are easier to describe. Our ideas for general graphs originated by considering bipartite graphs. Here, we choose LL to be one side of the bipartition. Then, the expected sampling cost in the first phase is exactly ∑e∈Ecexe\sum_{e\in E}c_ex_e. 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 u∈V∖Lu\in V\setminus L by at most 1e∑e∈δ(u)cexe\frac{1}{\sqrt{e}}\sum_{e\in\delta(u)}c_ex_e (this is the non-trivial part of the argument). Thus, the total expected cost is (1+1e)\left(1+\frac{1}{\sqrt{e}}\right) times the cost of the LP.

For general simple graphs (that may not be bipartite), we include each vertex into LL independently with probability θ\theta. Then, the expected sampling cost is at most 2θ∑e∈Ecexe2\theta\sum_{e\in E}c_ex_e. Conditional on a vertex uu lying outside LL, its incident edge ee is independently chosen in the first phase set FF with probability θxe\theta x_e; we use this fact to show that the expected augmentation cost in the second phase at each remaining vertex u∈V∖Lu \in V \setminus L is at most e−θ/2∑e∈δ(u)cexee^{-\theta/2}\sum_{e\in\delta(u)}c_ex_e. Thus, the total expected cost is (2θ+2(1−θ)e−θ/2)∑e∈Ecexe(2\theta+2(1-\theta)e^{-\theta/2})\sum_{e\in E}c_ex_e leading to an approximation factor of

2θ+2(1−θ)e−θ/2.2\theta+2(1-\theta)e^{-\theta/2}.

Choosing θ≈0.47008\theta\approx0.47008 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 LP1LP_1 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 pp-Edge-Cover remains tractable through bb-matching [32]. In Colorful Edge Cover problem, vertices are colored and the goal is to cover at least rir_i vertices of color ii for each color ii 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 (17/16−ϵ)(17/16-\epsilon)-approximation for this problem for every constant ϵ>0\epsilon> 0. 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 G=(V,E)G=(V,E) and the goal is to find a minimum cardinality subset SS of vertices such that every edge has at least one endpoint in SS. Chlebík and Chlebíková [19] showed that Vertex-Cover in simple cubic graphs is NP-hard to approximate within a factor of 10099−ϵ\frac{100}{99}-\epsilon for every ϵ>0\epsilon> 0.

Proof of Theorem 1.1. We reduce minimum cardinality vertex cover in simple cubic graphs to Flex-Edge-Cover. Let G=(V,E)G=(V,E) be an instance of minimum cardinality vertex cover. We set p=1p=1 and q=2q=2, construct a graph G′=(V′,E′)G'=(V',E') and cost function c′:E′→Z≥0c':E' \to\mathbb{Z}_{\ge0} as follows. The set V′V' consists of 3 copies sv,rv,rv′s_v,r_v,r'_v of each vertex v∈Vv\in V and 5 vertices xe,ae1,ae2,be1,be2x_e,a^1_e,a^2_e,b^1_e,b^2_e for each edge e∈Ee\in E. The set E′E' consists of safe edges svrvs_vr_v with csvrv′=2c'_{s_vr_v}=2 for each v∈Vv\in V, safe edges rvrv′r_vr'_v with crvrv′′=0c'_{r_vr'_v}=0 for each v∈Vv\in V, unsafe edges xesvx_es_v and xesux_es_u with cxesv′=cxesu′=1c'_{x_es_v}=c'_{x_es_u}=1 for each e=uw∈Ee=uw\in E, unsafe edges xeaeix_ea^i_e with cxeaei′=0c'_{x_ea^i_e}=0 for each i∈[2]i\in[2] and e∈Ee\in E, safe edges aeibeia^i_eb^i_e with caeibei′=0c'_{a^i_eb^i_e}=0 for each i∈[2]i \in[2] and e∈Ee \in E. We note that the constructed graph G′G' is simple bipartite with bipartition X={xe,bei}e∈E,i∈[2]∪{rv}v∈VX = \{x_e, b_e^i\}_{e \in E,i \in[2]} \cup\{r_v\}_{v \in V} and V′∖XV' \setminus X. See Figure 1 for an illustration of G′G'. Let τ(G)\tau(G) be the value of the smallest vertex cover in GG and OPTOPT be the optimal value of Flex-Edge-Cover on G′G'.

An illustration of the construction of $G'$

Figure 1. An illustration of the construction of G′G'. 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 G′G'.

Let C⊆VC \subseteq V be a vertex cover of GG. We construct a subset F⊆E′F \subseteq E' as follows. For every vertex v∈Cv \in C, add the three unsafe edges of the form xesvx_es_v to FF. For every vertex v∉Cv \notin C add the safe edges svrvs_vr_v and rvrv′r_vr'_v to FF. Lastly add the edges xeaeix_ea_e^i and aeibeia_e^ib_e^i for all e∈Ee \in E, i∈{1,2}i \in\{1,2\}. We observe that FF is feasible for Flex-Edge-Cover on instance (G′,p,q,c′)(G',p,q,c'). We have that c′(F)=3∣C∣+2(∣V∣−∣C∣)=2∣V∣+∣C∣c'(F) = 3|C| + 2(|V| - |C|) = 2|V| + |C|, and hence, OPT≤2∣V∣+τ(G)OPT \leq2|V| + \tau(G).

Next, let FF be a feasible solution to the Flex-Edge-Cover instance (G′,p,q,c′)(G',p,q,c'). Let CF={v∈V∣svxe∈F for some e∈E}C_F = \{v \in V \mid s_vx_e \in F \text{ for some } e \in E\}. We show that CFC_F is a vertex cover in GG. Fix an edge e∈Ee \in E. Since the vertex xex_e is incident to 4 edges, which are all unsafe, we must have that dF(xe)≥3d_F(x_e) \geq3 by definition of FF. Since 2 of the edges incident to xex_e are of the form svxes_vx_e, by the pigeonhole principle, FF contains an edge suxes_ux_e for some vertex u∈Vu \in V. Since uu covers ee and u∈CFu \in C_F, CFC_F is a vertex cover. Next, we bound the size of the vertex cover CFC_F. If v∈V∖CFv \in V \setminus C_F, then edge svrvs_vr_v of cost 2 is in FF and so c′(δF(sv))≥2c'(\delta_F(s_v)) \geq2. Otherwise, suppose v∈CFv \in C_F. This implies that svxe′∈δF(sv)s_vx_{e'} \in\delta_F(s_v) for some e′∈Ee' \in E. If svrv∈δF(sv)s_vr_v \in\delta_F(s_v), then c′(δF(sv))≥3c'(\delta_F(s_v)) \geq3. Otherwise svrv∉δF(sv)s_vr_v \notin\delta_F(s_v) and so δF(sv)\delta_F(s_v) must contain the three edges of the form svxes_vx_e, which again implies c′(δF(sv))≥3c'(\delta_F(s_v)) \geq3. Thus, we conclude that

c′(F)≥∑v∈Vc′(δF(v))≥3∣CF∣+2∣V∖CF∣=2∣V∣+∣CF∣(4)c'(F) \geq\sum_{v \in V} c'(\delta_F(v)) \geq3|C_F| + 2|V \setminus C_F| = 2|V| + |C_F| \tag*{(4)}

Therefore, we have that OPT≥2∣V∣+τ(G)OPT \geq2|V| + \tau(G). Since we showed earlier that the reverse inequality holds, we have that

OPT=2∣V∣+τ(G)(5)OPT = 2|V| + \tau(G) \tag*{(5)}

For all simple graphs H=(VH,EH)H = (V_H,E_H), we have that τ(H)≥∣EH∣Δ(H)\tau(H) \geq\frac{|E_H|}{\Delta(H)}. This follows since given any vertex cover CC of HH, we have that ∣C∣(Δ(H))≥∑v∈CdH(v)≥∣EH∣|C|(\Delta(H)) \geq\sum_{v \in C} d_H(v) \geq|E_H|. If HH is a cubic graph we have that τ(H)≥∣VH∣2\tau(H) \geq\frac{|V_H|}{2}. Thus, 2∣VH∣+τ(H)≤5τ(H)2|V_H| + \tau(H) \leq5\tau(H) for all cubic graphs HH. Suppose we had a ρ\rho-approximation to Flex-Edge-Cover on instance (G′,p,q,c′)(G',p,q,c') that returned a solution FF. From the previous analysis, CFC_F is a vertex cover in GG. We have that

∣CF∣≤c′(F)−2∣V∣≤ρOPT−2∣V∣=ρ(2∣V∣+τ(G))−2∣V∣=(ρ−1)(2∣V∣+τ(G))+τ(G)≤(ρ−1)(5τ(G))+τ(G)=(5ρ−4)τ(G)(6)\begin{aligned} |C_F| &\leq c'(F)-2|V| \\ &\leq\rho OPT-2|V| \\ &= \rho(2|V|+\tau(G))-2|V| \\ &= (\rho-1)(2|V|+\tau(G))+\tau(G) \\ &\leq(\rho-1)(5\tau(G))+\tau(G) \\ &= (5\rho-4)\tau(G) \tag*{(6)} \end{aligned}

where (4) follows from (2), (5) follows from (3), and (6) follows from the fact that GG is cubic. Thus, a ρ\rho-approximation for Flex-Edge-Cover would give a 5ρ−45\rho-4 approximation to minimum cardinality vertex cover on cubic graphs. This implies that a 496495−ϵ\frac{496}{495}-\epsilon approximation for Flex-Edge-Cover would yield a 5(496495−ϵ)−4=10099−5ϵ5\left(\frac{496}{495}-\epsilon\right)-4=\frac{100}{99}-5\epsilon 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 (x,α,β,λ)(x,\alpha,\beta,\lambda) to (LP2)(LP_2) and will round it. The rounding algorithm additionally takes a subset L⊆VL\subseteq V as input whose significance will be clear shortly. The rounding algorithm proceeds in two phases. The algorithm addresses the covering requirements of vertices in LL in the first phase as follows: let v∈Lv\in L. By Lemma 1.4, xδ(v)x_{\delta(v)} is a convex combination of safe-satisfying vectors and cumulative-satisfying vectors (i.e., vectors in Av\mathcal{A}_v and Bv\mathcal{B}_v). The algorithm samples a vector FvF_v 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 F1=⋃v∈LFvF_1=\bigcup_{v\in L}F_v. We observe that each v∈Lv\in L is either safe-covered or cumulative-covered by FvF_v and hence, by F1F_1 and moreover, the expected cost of F1F_1 is at most the cost of the LP solution (since LL is an independent set and consequently δ(a)∩δ(b)=∅\delta(a)\cap\delta(b)=\emptyset for every a,b∈La,b\in L). However, we could have vertices u∈V∖Lu\in V\setminus L that are uncovered by F1F_1 (i.e., neither cumulative-covered nor safe-covered). The algorithm addresses the covering-requirements for vertices in V∖LV\setminus L in the second phase as follows: for each u∈V∖Lu\in V\setminus L, it computes a cheapest augmentation set Au1A_u^1 to F1F_1 that makes uu safe-covered (by greedy), a cheapest augmentation set Au2A_u^2 to F1F_1 that makes uu cumulative-covered (by greedy), and sets Au:=arg⁡min⁡{c(Au1),c(Au2)}A_u:=\arg\min\{c(A_u^1),c(A_u^2)\}. It sets the solution of the second phase as F2=⋃u∈RAuF_2=\bigcup_{u\in R}A_u and returns F1∪F2F_1\cup F_2. See Algorithm 1 for a formal description.

Essentially, the algorithm uses the LP solution to sample and satisfy the covering requirements for vertices in LL 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 V∖LV\setminus L. If L=∅L=\emptyset, 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 LL 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 L⊆VL \subseteq V, Algorithm 1 returns a feasible flexible-edge-cover for the instance (G,p,q)(G,p,q).

Proof. Let FF be the solution returned by the algorithm for the input instance (G,p,q)(G,p,q) with a feasible solution (x,α,β,λ)(x,\alpha,\beta,\lambda) to (LP2)(LP_2). We show that every vertex v∈L∪Rv \in L \cup R is either safe-covered or cumulative-covered by FF.

Let v∈Lv \in L. We recall that xδ(v)=∑a∈Av∪Bvaλax_{\delta(v)} = \sum_{a\in\mathcal{A}_v\cup\mathcal{B}_v}a\lambda_a with ∑a∈Av∪Bvλa=1\sum_{a\in\mathcal{A}_v\cup\mathcal{B}_v}\lambda_a = 1 and λa≥0\lambda_a \ge0 for all a∈Av∪Bva \in\mathcal{A}_v \cup\mathcal{B}_v. For each a∈Ava \in\mathcal{A}_v, we have that vv is safe-covered by support⁡(a)\operatorname{support}(a) and for each a∈Bva \in\mathcal{B}_v, we have that vv is cumulative-covered by support⁡(a)\operatorname{support}(a). Thus, for each a∈Av∪Bva \in\mathcal{A}_v \cup\mathcal{B}_v, we have that vv is either safe-covered or cumulative-covered by support⁡(a)\operatorname{support}(a). Hence, vv is either safe-covered or cumulative-covered by F1⊆FF_1 \subseteq F.

Next, consider u∈Ru \in R. We have two cases: (i) Suppose Au=Au1A_u = A_u^1. We recall that

Au1=arg⁡min⁡{c(A):A⊆δS(u)∖F1, ∣(δ(F1∩S)∪A(u))∣≥p}A_u^1 = \arg\min\{c(A) : A \subseteq\delta_S(u) \setminus F_1,\ \lvert(\delta(F_1\cap S)\cup A(u))\rvert\ge p\}

and hence, ∣δ(F1∪Au1)∩S(u)∣≥p\lvert\delta_{(F_1\cup A_u^1)\cap S}(u)\rvert\ge p. Consequently, uu is safe-satisfied by F1∪Au⊆FF_1 \cup A_u \subseteq F. (ii) Suppose Au=Au2A_u = A_u^2. We recall that

Au2=arg⁡min⁡{c(A):A⊆δ(u)∖F1, ∣δF1∪A(u)∣≥p+q}A_u^2 = \arg\min\{c(A) : A \subseteq\delta(u) \setminus F_1,\ \lvert\delta_{F_1\cup A}(u)\rvert\ge p+q\}

and hence, ∣δF1∪Au2(u)∣≥p+q\lvert\delta_{F_1\cup A_u^2}(u)\rvert\ge p+q. Consequently, uu is cumulative-satisfied by F1∪Au⊆FF_1 \cup A_u \subseteq F.

The rest of the section is devoted to analyzing the approximation factor via a careful choice of LL 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 F1F_1 is small relative to the LP. In the second step, we augment F1F_1 with additional edges in a greedy manner to fix the covering requirements of vertices in V∖LV \setminus L. 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 (LP2)(LP_2). In Section 3.3, we specify the choice of LL and design a 1.606-approximation for simple bipartite graphs. In Section 3.4, we specify the choice of LL 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 aa, we use the convention that (a)+=max⁡{a,0}(a)^+ = \max\{a,0\}.

Key Technical Lemma

In this section, we show the following key technical lemma that compares the cost of the cheapest rr-element subset to the cost of the cheapest augmentation AA to a randomly sampled subset FF to achieve ∣A∪F∣≥r|A \cup F| \ge r.

Lemma 3.3. Let NN be a ground set with cost function c:N→R≥0c:N \to\mathbb{R}_{\ge0} and r∈Z+r \in\mathbb{Z}_+ be a positive integer. Let Cr=min⁡{c(C):C⊆N,∣C∣=r}C_r = \min\{c(C): C \subseteq N, |C| = r\}, i.e., CrC_r is the sum of the costs of the cheapest rr elements of NN. Let α>0\alpha> 0 and x,y∈[0,1]Nx,y \in[0,1]^N such that 0≤αyi≤xi≤10 \le\alpha y_i \le x_i \le1 for all i∈Ni \in N and y(N)≥ry(N) \ge r. Let F⊆NF \subseteq N be a random set obtained by selecting each element i∈Ni \in N with probability xix_i independently. Then,

EF[min⁡{c(F′):F′⊆N∖F, ∣F′∪F∣≥r}]≤e−αCr.\mathbb{E}_F\left[\min\{c(F'): F' \subseteq N \setminus F,\ |F' \cup F| \ge r\}\right] \le e^{-\alpha} C_r.

We need the following helper lemma to prove Lemma 3.3.

Lemma 3.4. Let {Xi}i=1n\{X_i\}_{i=1}^n be independent Bernoulli variables with xi=E[Xi]x_i = \mathbb{E}[X_i], μ=∑i=1nxi\mu= \sum_{i=1}^n x_i, and Y:=∑i=1nXiY := \sum_{i=1}^n X_i. For every non-negative integer a∈Z>0a \in\mathbb{Z}_{>0}, we have that

E[(a−Y)+]≤ae−μa.\mathbb{E}[(a-Y)^+] \le ae^{-\frac{\mu}{a}}.

Proof. Let y,a∈Z≥0y,a \in\mathbb{Z}_{\ge0}. We have that a(1−ya)≤a(1−1a)ya(1-\frac{y}{a}) \le a(1-\frac{1}{a})^y by convexity of the function f:[0,1]→Rf:[0,1] \to\mathbb{R} given by f(x)=(1−x)yf(x)=(1-x)^y. Thus, we have that (a−y)+≤a(1−1a)y(a-y)^+ \le a(1-\frac{1}{a})^y. Hence,

E[(a−Y)+]≤aE[(1−1a)Y]=aE[(1−1a)∑i=1nXi]=a∏i=1mE[(1−1a)Xi](7)\begin{aligned} \mathbb{E}[(a-Y)^+] \le a\mathbb{E}\left[\left(1-\frac{1}{a}\right)^Y\right] \\ &= a\mathbb{E}\left[\left(1-\frac{1}{a}\right)^{\sum_{i=1}^n X_i}\right] \\ &= a\prod_{i=1}^m \mathbb{E}\left[\left(1-\frac{1}{a}\right)^{X_i}\right] \tag*{(7)} \end{aligned}
=a∏i=1m(1−xia)(8)= a\prod_{i=1}^m\left(1-\frac{x_i}{a}\right) \tag*{(8)}
≤ae−μ/a.(9)\le ae^{-\mu/a}. \tag*{(9)}

where (7) is by independence of {Xi}i=1n\{X_i\}_{i=1}^n, (8) is because XiX_i takes values in {0,1}\{0,1\} for every i∈[n]i \in[n], and (9) is by convexity of the function f(x)=exf(x)=e^x.

We now prove Lemma 3.3.

Proof of Lemma 3.3. For a real value tt, we define N≥t:={i∈N:ci≥t}N_{\ge t}:=\{i\in N:c_i\ge t\} and N<t:={i∈N:ci<t}N_{<t}:=\{i\in N:c_i<t\}. For a positive integer r∈Z+r\in\mathbb{Z}_+ and a real value tt, we define rt=(r−∣N<t∣)+r_t=(r-|N_{<t}|)^+. For a subset F⊆NF\subseteq N and a positive integer r∈Z+r\in\mathbb{Z}_+, we define AF,r:=min⁡{c(F′):F′⊆N∖F, ∣F′∪F∣≥r}A_{F,r}:=\min\{c(F'):F'\subseteq N\setminus F,\ |F'\cup F|\ge r\}. We define ZF=arg⁡min⁡{c(F′):F′⊆N∖F, ∣F′∪F∣≥r}Z_F=\arg\min\{c(F'):F'\subseteq N\setminus F,\ |F'\cup F|\ge r\}. For a set A⊂RA\subset\mathbb{R}, we denote the real-valued function 1A:R→R\mathbf{1}_A:\mathbb{R}\to\mathbb{R} as 1A(t)=1\mathbf{1}_A(t)=1 if t∈At\in A and 1A(t)=0\mathbf{1}_A(t)=0 if t∉At\notin A.

We need to show that EF[∑i∈ZFci]≤e−αCrE_F[\sum_{i\in Z_F}c_i]\le e^{-\alpha C_r}. Let us fix a set FF and consider ZFZ_F. We can express ∑i∈ZFci\sum_{i\in Z_F}c_i as ∑i∈ZF(∫0∞1[0,ci](t) dt)\sum_{i\in Z_F}(\int_0^\infty\mathbf{1}_{[0,c_i]}(t)\,dt). Swapping the order of the finite sum and the integral gives

∑i∈ZFci=∫0∞∑i∈ZF1[0,ci](t) dt.\sum_{i\in Z_F}c_i=\int_0^\infty\sum_{i\in Z_F}\mathbf{1}_{[0,c_i]}(t)\,dt.

We will use the following claim to simplify ∑i∈ZF1[0,ci]\sum_{i\in Z_F}\mathbf{1}_{[0,c_i]} for a fixed t≥0t\ge0.

Claim 3.5. Let t≥0t\ge0. Then, ∑i∈ZF1[0,ci](t)=(r−∣N<t∣−∣F∩N≥t∣)+\sum_{i\in Z_F}\mathbf{1}_{[0,c_i]}(t)=(r-|N_{<t}|-|F\cap N_{\ge t}|)^+.

Proof. We note that ∑i∈ZF1[0,ci](t)\sum_{i\in Z_F}\mathbf{1}_{[0,c_i]}(t) counts exactly the elements in ZFZ_F that have cost at least tt. Since ZF⊆N∖FZ_F\subseteq N\setminus F, ∑i∈ZF1[0,ci](t)=∣ZF∩(N≥t∖F)∣\sum_{i\in Z_F}\mathbf{1}_{[0,c_i]}(t)=|Z_F\cap(N_{\ge t}\setminus F)|. We first show that ∣ZF∩(N≥t∖F)∣=(∣ZF∣−∣(N<t∖F)∣)+|Z_F\cap(N_{\ge t}\setminus F)|=(|Z_F|-|(N_{<t}\setminus F)|)^+ by considering two cases:

Case (i). ∣ZF∣>∣N<t∖F∣|Z_F|>|N_{<t}\setminus F|. Since ZFZ_F is a subset of N∖FN\setminus F that contains the cheapest ∣ZF∣|Z_F| items of N∖FN\setminus F, ZFZ_F contains all the items in N<t∖FN_{<t}\setminus F and hence contains the cheapest ∣ZF∖N<t∣|Z_F\setminus N_{<t}| items of N≥t∖FN_{\ge t}\setminus F. Thus, in this case there are exactly ∣ZF∣−∣N<t∖F∣|Z_F|-|N_{<t}\setminus F| elements in ZFZ_F that have cost at least tt.

Case (ii). ∣ZF∣≤∣N<t∖F∣|Z_F|\le|N_{<t}\setminus F|. In this case, ZFZ_F does not contain elements with cost at least tt. Thus ZFZ_F has exactly (∣ZF∣−∣(N<t∖F)∣)+(|Z_F|-|(N_{<t}\setminus F)|)^+ with cost at least tt.

Now, we have that

(∣ZF∣−∣(N<t∖F)∣)+=(ZF−∣N<t∣+∣F∩N<t∣)+=(r−∣F∣−∣N<t∣+∣F∩N<t∣)+=(r−∣N<t∣−∣F∩N≥t∣)+.(10)\begin{aligned} (|Z_F|-|(N_{<t}\setminus F)|)^+ &=(Z_F-|N_{<t}|+|F\cap N_{<t}|)^+\\ &=(r-|F|-|N_{<t}|+|F\cap N_{<t}|)^+\\ &=(r-|N_{<t}|-|F\cap N_{\ge t}|)^+. \tag*{(10)} \end{aligned}

where (10) follows from the fact that ∣F∪ZF∣=r|F\cup Z_F|=r.

By Claim 3.5, we have that

∑i∈ZFci=∫0∞(∑i∈ZF1[0,ci](t))dt=∫0∞(r−∣N<t∣−∣F∩N≥t∣)+dt.\sum_{i\in Z_F}c_i=\int_0^\infty\left(\sum_{i\in Z_F}\mathbf{1}_{[0,c_i]}(t)\right)dt=\int_0^\infty(r-|N_{<t}|-|F\cap N_{\ge t}|)^+dt.

We note that (r−∣N<t∣−∣F∩N≥t∣)+≤((r−∣N<t∣)+−∣F∩N≥t∣)+=(rt−∣F∩N≥t∣)+(r-|N_{<t}|-|F\cap N_{\ge t}|)^+\le((r-|N_{<t}|)^+-|F\cap N_{\ge t}|)^+=(r_t-|F\cap N_{\ge t}|)^+, which implies that

∑i∈ZFci≤∫0∞(rt−∣F∩N≥t∣)+dt.\sum_{i\in Z_F}c_i\le\int_0^\infty(r_t-|F\cap N_{\ge t}|)^+dt.

Hence, we have that

EF[∑i∈ZFci]≤EF[∫0∞(rt−∣F∩N≥t∣)+dt]=∫0∞EF[(rt−∣F∩N≥t∣)+]dt.E_F\left[\sum_{i\in Z_F}c_i\right]\le E_F\left[\int_0^\infty(r_t-|F\cap N_{\ge t}|)^+dt\right]=\int_0^\infty E_F[(r_t-|F\cap N_{\ge t}|)^+]dt.

Let us fix t≥0t \ge0 and consider EF[(rt−∣F∩N≥t∣)+]E_F[(r_t-|F\cap N_{\ge t}|)^+]. Lemma 3.4 implies that for rt>0r_t>0, E[(rt−∣F∩N≥t∣)+]≤rte−x(N≥t)/rtE[(r_t-|F\cap N_{\ge t}|)^+] \le r_t e^{-x(N_{\ge t})/r_t}. If rt=0r_t=0, then trivially E[(rt−∣F∩N≥t∣)+]=0E[(r_t-|F\cap N_{\ge t}|)^+]=0. Thus, we have that

∫0∞E[(rt−∣F∩N≥t∣)+] dt≤∫{t:t≥0,rt>0}rte−x(N≥t)/rt dt≤∫{t:t≥0,rt>0}rte−αy(N≥t)/rt dt(11)\int_0^\infty E\left[(r_t-|F\cap N_{\ge t}|)^+\right]\,dt \le\int_{\{t:t\ge0,r_t>0\}} r_t e^{-x(N_{\ge t})/r_t}\,dt \le\int_{\{t:t\ge0,r_t>0\}} r_t e^{-\alpha y(N_{\ge t})/r_t}\,dt \tag*{(11)}
=∫{t:t≥0,rt>0}rte−α(y(N)−y(N<t))/rt dt≤e−α∫{t:t≥0,rt>0}rt dt(12)= \int_{\{t:t\ge0,r_t>0\}} r_t e^{-\alpha(y(N)-y(N_{<t}))/r_t}\,dt \le e^{-\alpha}\int_{\{t:t\ge0,r_t>0\}} r_t\,dt \tag*{(12)}

where (11) follows from the hypothesis that xi≥αyix_i\ge\alpha y_i for all i∈Ni\in N and (12) follows from the fact that y(N)−Y(N<t)≥r−∣N<t∣=rty(N)-Y(N_{<t})\ge r-|N_{<t}|=r_t for rt>0r_t>0. We now bound ∫0∞rt dt\int_0^\infty r_t\,dt. Without loss of generality, let the items be ordered such that c1≤c2⋯≤c∣N∣c_1\le c_2\cdots\le c_{|N|} and let c0=0c_0=0. For t∈(ci,ci+1]t\in(c_i,c_{i+1}], we have that rt=(r−N<t)+=(r−i)+r_t=(r-N_{<t})^+=(r-i)^+. Thus,

∫0∞rt dt=∑i=0n−1(r−i)+(ci+1−ci)=∑i=0r−1(r−i)(ci+1−ci)=(rcr−(r−1)cr+∑i=1r−1ci)=Cr.\int_0^\infty r_t\,dt =\sum_{i=0}^{n-1}(r-i)^+(c_{i+1}-c_i) =\sum_{i=0}^{r-1}(r-i)(c_{i+1}-c_i) =\left(rc_r-(r-1)c_r+\sum_{i=1}^{r-1}c_i\right) =C_r.

Thus, EF[∑i∈ZFci]≤e−αCrE_F[\sum_{i\in Z_F}c_i]\le e^{-\alpha}C_r.

Augmentation Cost

We now use Lemma 3.3 to bound the augmentation cost of covering a vertex uu after sampling the edges incident to it according to a distribution that depends on xδ(u)x_{\delta(u)}.

Lemma 3.6. Let (G=(V,E),p,q,c:E→R≥0)(G=(V,E),p,q,c:E\to\mathbb{R}_{\ge0}) be the input instance of Flex-Edge-Cover, (x,α,β,λ)(x,\alpha,\beta,\lambda) be a feasible solution to (LP2)(LP_2). Let u∈Vu\in V and θ∈[0,1]\theta\in[0,1]. Let Fu⊆δ(u)F_u\subseteq\delta(u) denote the set of edges obtained by sampling each edge e∈δ(u)e\in\delta(u) independently with probability θxe\theta x_e. Let

Au1:=arg⁡min⁡{c(A):A⊆δS(u)∖Fu, ∣(δ(Fu∪A)∩S(u))∣≥p}A_u^1:=\arg\min\{c(A):A\subseteq\delta_S(u)\setminus F_u,\ |(\delta(F_u\cup A)\cap S(u))|\ge p\}
Au2:=arg⁡min⁡{c(A):A⊆δ(u)∖Fu, ∣δFu∪A(u)∣≥p+q}A_u^2:=\arg\min\{c(A):A\subseteq\delta(u)\setminus F_u,\ |\delta_{F_u\cup A}(u)|\ge p+q\}
Au:=arg⁡min⁡{c(Au1),c(Au2)}.A_u:=\arg\min\{c(A_u^1),c(A_u^2)\}.

Then,

E[c(Au)]≤e−θ2∑e∈δ(u)cexe.E[c(A_u)]\le e^{-\frac{\theta}{2}}\sum_{e\in\delta(u)}c_e x_e.

Proof of Lemma 3.6. We define

Cp:=min⁡{c(F):F⊆δS(u), ∣F∣=p}C_p:=\min\{c(F):F\subseteq\delta_S(u),\ |F|=p\}
Dp+q:=min⁡{c(F):F⊆δ(u), ∣F∣=p+q}.D_{p+q}:=\min\{c(F):F\subseteq\delta(u),\ |F|=p+q\}.

By the first part of Lemma 1.4, we have that xδ(u)=λuau+(1−λu)bux_{\delta(u)}=\lambda_u a^u+(1-\lambda_u)b^u where au∈conv⁡(Au)a^u\in\operatorname{conv}(A_u) and bu∈conv⁡(Bu)b^u\in\operatorname{conv}(B_u). Thus, 0≤θλuau≤θxδ(u)0\le\theta\lambda_u a^u\le\theta x_{\delta(u)} and 0≤θ(1−λu)bu≤xδ(u)≤10\le\theta(1-\lambda_u)b^u\le x_{\delta(u)}\le1 and moreover, au(δ(u))≥pa^u(\delta(u))\ge p and bu(δ(u))≥p+qb^u(\delta(u))\ge p+q. Applying Lemma 3.3 to N=δ(u)N=\delta(u) with cost function c:δ(u)→R≥0c:\delta(u)\to\mathbb{R}_{\ge0}, r=pr=p, α=λu\alpha=\lambda_u, y=auy=a^u, we obtain that

E[c(Au1)]≤e−θλuCp.E[c(A_u^1)]\le e^{-\theta\lambda_u}C_p.

Applying Lemma 3.3 to N=δ(u)N=\delta(u) with cost function c:δ(u)→R≥0c:\delta(u)\to\mathbb{R}_{\ge0}, r=p+qr=p+q, α=1−λu\alpha=1-\lambda_u, y=buy=b^u, we obtain that

E[c(Au2)]≤e−θ(1−λu)Dp+q.E[c(A_u^2)]\le e^{-\theta(1-\lambda_u)}D_{p+q}.

Consequently, we have that

E[c(Au)]=E[min⁡{c(Au1),c(Au2)}]≤min⁡{E[c(Au1)],E[c(Au2)]}≤min⁡{e−θλuCp,e−θ(1−λu)Dp+q}≤(e−θλuCp)λu(e−θ(1−λu)Dp+q)1−λu=e−θ(λu2+(1−λu)2)CpλuDp+q1−λu(13)\begin{aligned} E[c(A_u)]&=E\left[\min\left\{c(A_u^1),c(A_u^2)\right\}\right]\\ &\le\min\left\{E\left[c(A_u^1)\right],E\left[c(A_u^2)\right]\right\}\\ &\le\min\left\{e^{-\theta\lambda_u}C_p,e^{-\theta(1-\lambda_u)}D_{p+q}\right\}\\ &\le\left(e^{-\theta\lambda_u}C_p\right)^{\lambda_u}\left(e^{-\theta(1-\lambda_u)}D_{p+q}\right)^{1-\lambda_u} \\ &=e^{-\theta(\lambda_u^2+(1-\lambda_u)^2)}C_p^{\lambda_u}D_{p+q}^{1-\lambda_u} \tag*{(13)} \end{aligned}
≤e−θ(λu2+(1−λu)2)(λuCp+(1−λu)Dp+q)(14)\le e^{-\theta(\lambda_u^2+(1-\lambda_u)^2)}\left(\lambda_u C_p+(1-\lambda_u)D_{p+q}\right) \tag*{(14)}
≤e−θ2(λuCp+(1−λu)Dp+q)(15)\le e^{-\frac{\theta}{2}}\left(\lambda_u C_p+(1-\lambda_u)D_{p+q}\right) \tag*{(15)}
≤e−θ2(λu∑e∈δ(u)ceaeu+(1−λu)∑e∈δ(u)cebeu)(16)\le e^{-\frac{\theta}{2}}\left(\lambda_u\sum_{e\in\delta(u)}c_ea_e^u+(1-\lambda_u)\sum_{e\in\delta(u)}c_eb_e^u\right) \tag*{(16)}
=e−θ2(∑e∈δ(u)cexe),(17)=e^{-\frac{\theta}{2}}\left(\sum_{e\in\delta(u)}c_ex_e\right), \tag*{(17)}

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 θ≥0\theta\ge0 and λ2+(1−λ)2≥1/2\lambda^2+(1-\lambda)^2\ge1/2 for all λ∈[0,1]\lambda\in[0,1], inequality (16) is because au∈conv⁡(Au)a^u\in\operatorname{conv}(A_u) and bu∈conv⁡(Bu)b^u\in\operatorname{conv}(B_u), and inequality (17) is because xδ(u)=λuau+(1−λu)bux_{\delta(u)}=\lambda_u a^u+(1-\lambda_u)b^u.

Bipartite Graphs

Suppose the input graph is G=(V,E)G=(V,E) is bipartite. We pick LL to be one part of a valid bipartition of GG 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 (G,p,q,c)(G,p,q,c) be a bipartite input instance of Flex-Edge-Cover. Let FF be the solution returned by Algorithm 1 implemented with LL being one part of a valid bipartition of GG. Then,

E[c(F)]≤(1+1e)∑e∈Ecexe.E[c(F)]\le\left(1+\frac{1}{\sqrt{e}}\right)\sum_{e\in E}c_ex_e.

Proof. We observe that F=F1⊎F2F=F_1\uplus F_2 and hence, c(F)=c(F1)+c(F2)c(F)=c(F_1)+c(F_2). We bound the expected cost of F1F_1 and F2F_2 separately. First, we bound E[c(F1)]E[c(F_1)]. We have that

E[c(F1)]=∑v∈LE[c(Fv)]=∑v∈L∑e∈δ(v)cexe=∑e∈Ecexe.E[c(F_1)]=\sum_{v\in L}E[c(F_v)]=\sum_{v\in L}\sum_{e\in\delta(v)}c_ex_e=\sum_{e\in E}c_ex_e.

The first and third equalities are owing to the bipartiteness of GG. The second equality is because for each v∈Lv \in L, for each edge e∈δ(v)e \in\delta(v), the probability of sampling ee into FvF_v is exactly xex_e.

Next, we bound E[c(F2)]E[c(F_2)]. Let u∈V∖Lu \in V \setminus L. For each e∈δ(u)e \in\delta(u), the edge ee is sampled into F1F_1 independently with probability xex_e; independence holds because GG is a simple graph and the probability of sampling ee into F1F_1 depends only on the distribution at the other end-vertex v∈Lv \in L of ee. Independence allows us to apply Lemma 3.6. Hence, applying Lemma 3.6 with θ=1\theta= 1, we have that

E[c(Au)]≤1e∑e∈δ(u)cexe.E[c(A_u)] \le\frac{1}{\sqrt{e}} \sum_{e \in\delta(u)} c_e x_e.

Hence,

E[c(F2)]=∑u∈RE[c(Au)]≤1e∑u∈R∑e∈δ(u)cexe=1e∑e∈Ecexe.E[c(F_2)] = \sum_{u \in R} E[c(A_u)] \le\frac{1}{\sqrt{e}} \sum_{u \in R} \sum_{e \in\delta(u)} c_e x_e = \frac{1}{\sqrt{e}} \sum_{e \in E} c_e x_e.

Again, the first and third equalities are owing to the bipartiteness of GG. Consequently, E[c(F)]=E[c(F1)+c(F2)]≤(1+1/e)∑e∈EcexeE[c(F)] = E[c(F_1) + c(F_2)] \le(1 + 1/\sqrt{e}) \sum_{e \in E} c_e x_e.

Remark 3.8. We note that this algorithm cannot be de-randomized in the natural way; the natural procedure is for each vertex v∈Lv \in L, compute a subset FvF_v that has the cheapest p+qp+q edges incident to vv and for each vertex u∈Ru \in R, compute the subset AuA_u. In the worst case, this procedure has an approximation factor asymptotically approaching two (see § 5.2).

Non-Bipartite Graphs

The choice of LL for bipartite graphs informs our rounding strategy for non-bipartite graphs. For bipartite graphs, we had the bipartition LL and V∖LV \setminus L of vertices and our algorithm proceeded in two phases: we used the LP solution to sample and satisfy the covering requirements for vertices in LL 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 V∖LV \setminus L. For non-bipartite graphs, it is unclear how to pick the subset LL 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 L=∅L = \emptyset in the first phase and augment to meet the covering requirements of vertices in R=VR = V 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 L=VL = V in the first phase and augment to meet the covering requirements of vertices in R=∅R = \emptyset 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 LL, we randomly sample each vertex u∈Vu \in V into the first phase set LL with probability θ\theta (where the value of θ\theta will be chosen later). For θ=0.47008\theta= 0.47008, we run Algorithm 1 for such a random choice of LL. We now show that this rounding strategy achieves an approximation ratio of 1.78.

Lemma 3.9. Let FF be the solution returned by Algorithm 1 implemented for a random set LL, where LL is obtained by picking each vertex v∈Vv \in V into LL with probability θ=0.47008\theta= 0.47008. Then,

E[c(F)]≤1.78∑e∈Ecexe.E[c(F)] \le1.78 \sum_{e \in E} c_e x_e.

:::`

Proof. We observe that F=F1⊎F2F = F_1 \uplus F_2 and hence, c(F)=c(F1)+c(F2)c(F) = c(F_1) + c(F_2). We bound the expected cost of F1F_1 and F2F_2 separately. First, we bound E[c(F1)]E[c(F_1)]. We have that

EZ,F1[c(F1)]=∑v∈VPr⁡[v∈L]EFv[c(Fv)∣v∈L]=∑v∈VθEFv[c(Fv)∣v∈L]=∑v∈Vθ(∑e∈δ(v)cexe)=2θ(∑e∈Ecexe).\begin{aligned} E_{Z,F_1}[c(F_1)] = \sum_{v\in V} \Pr[v\in L]E_{F_v}[c(F_v)\mid v\in L] \\ &= \sum_{v\in V} \theta E_{F_v}[c(F_v)\mid v\in L] \\ &= \sum_{v\in V} \theta\left(\sum_{e\in\delta(v)} c_e x_e\right) \\ &= 2\theta\left(\sum_{e\in E} c_e x_e\right). \end{aligned}

The second equality is because each v∈Vv\in V is sampled into LL with probability θ\theta. The third equality is because for each v∈Vv\in V, for each edge e∈δ(v)e\in\delta(v), the probability of sampling ee into FvF_v is exactly xex_e. The final equality is because the cexec_e x_e term for each e∈Ee\in E is counted from the perspective of both end-vertices of ee.

Next, we bound E[c(F2)]E[c(F_2)]. We note that

EZ,F1[c(F2)]=∑u∈VPr⁡[u∈V∖L]EF1[c(Au)∣u∈V∖L].E_{Z,F_1}[c(F_2)] = \sum_{u\in V} \Pr[u\in V\setminus L]E_{F_1}[c(A_u)\mid u\in V\setminus L].

Let u∈Vu\in V. We have that Pr⁡[u∈V∖L]=1−θ\Pr[u\in V\setminus L] = 1-\theta. We now focus on EF1[c(Au)∣u∈V∖L]E_{F_1}[c(A_u)\mid u\in V\setminus L]. Condition on the event that u∈V∖Lu\in V\setminus L. For each e∈δ(u)e\in\delta(u), the edge ee is sampled into F1F_1 independently with probability θxe\theta x_e: This is because, the edge ee is present in F1F_1 only if the other end-vertex vv of ee is chosen into LL and conditioned on v∈Lv\in L, we have that ee is sampled into FvF_v with probability xex_e. The probability of vv being sampled into LL is θ\theta and conditioned on v∈Lv\in L, the probability of e∈Fve\in F_v is xex_e (since GG is simple); thus, the probability of e∈F1e\in F_1 is θxe\theta x_e. Moreover, independence holds because GG is a simple graph. Independence allows us to apply Lemma 3.6. Hence, applying Lemma 3.6 with θ\theta, we have that

E[c(Au)∣u∈V∖L]≤e−θ2∑e∈δ(u)cexe.E[c(A_u)\mid u\in V\setminus L] \le e^{-\frac{\theta}{2}}\sum_{e\in\delta(u)} c_e x_e.

Hence,

EZ,F1[c(F2)]=∑u∈VPr⁡[u∈V∖L]EF1[c(Au)∣u∈V∖L]=∑u∈V(1−θ)EF1[c(Au)∣u∈V∖L]≤∑u∈V(1−θ)e−θ2∑e∈δ(u)cexe=2(1−θ)e−θ2∑e∈Ecexe.\begin{aligned} E_{Z,F_1}[c(F_2)] = \sum_{u\in V} \Pr[u\in V\setminus L]E_{F_1}[c(A_u)\mid u\in V\setminus L] \\ &= \sum_{u\in V} (1-\theta)E_{F_1}[c(A_u)\mid u\in V\setminus L] \\ &\le\sum_{u\in V} (1-\theta)e^{-\frac{\theta}{2}}\sum_{e\in\delta(u)} c_e x_e \\ &= 2(1-\theta)e^{-\frac{\theta}{2}}\sum_{e\in E} c_e x_e. \end{aligned}

The second inequality is because each u∈Vu\in V is in V∖LV\setminus L with probability $1-\theta$. The final equality is because the cexec_e x_e term for each e∈Ee\in E is counted from the perspective of both end-vertices of $e.

Consequently, we have that

EZ,F1[c(F1)+c(F2)]≤2(θ+(1−θ)e−θ2)∑e∈Ecexe.E_{Z,F_1}[c(F_1)+c(F_2)] \leq2\left(\theta+(1-\theta)e^{-\frac{\theta}{2}}\right)\sum_{e\in E}c_e x_e.

For θ=0.47001\theta=0.47001, we have that 2θ+2(1−θ)e−θ/2=1.782\theta+2(1-\theta)e^{-\theta/2}=1.78, thus bounding the approximation factor. Our choice of θ=0.47001\theta=0.47001 is because the minimum value of the expression f(θ):=2θ+2(1−θ)e−θ/2f(\theta):=2\theta+2(1-\theta)e^{-\theta/2} over θ∈[0,1]\theta\in[0,1] occurs at θ∗=0.47001\theta^*=0.47001 with f(θ∗)=1.78f(\theta^*)=1.78 (since ff 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 G=(V,E=S⊎U)G=(V,E=S\uplus U), positive integers pp and qq, and a cost function c:E→R≥0c:E\to\mathbb{R}_{\geq0}. Here, the sets SS and UU are denoted as safe and unsafe edges, respectively. The goal is to find a subset F⊆EF\subseteq E with the least cost such that for every subset ∅≠X⊊V\varnothing\ne X\subsetneq V, FF has at least pp safe edges crossing the cut XX or p+qp+q edges crossing the cut XX.

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 GG 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 N=S⊎UN=S\uplus U, cost function c:N→R≥0c:N\to\mathbb{R}_{\geq0}, and positive integers pp and qq. The goal is to select a subset F⊆NF\subseteq N of minimum cost s.t. ∣F∩S∣≥p|F\cap S|\geq p or ∣F∣≥p+q|F|\geq p+q. Disjunctive-Knapsack-Cover can be solved in polynomial time as follows: Let FSF_S be the pp cheapest elements of SS and FF be the p+qp+q cheapest elements of NN. Output argmin{c(FS),c(F)}\mathop{\rm argmin}\{c(F_S),c(F)\}. 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.

min⁡∑e∈Ecexe(LP3)xe=αeR+βeR∀e∈δ(R), ∅≠R⊊VαR(δS(R))≥pλR∀∅≠R⊊VβR(δ(R))≥(p+q)(1−λR)∀∅≠R⊊V0≤αeR≤λR∀e∈δ(R), ∅≠R⊊V0≤βeR≤1−λR∀e∈δ(R), ∅≠R⊊V0≤λR≤1∀∅≠R⊊V(18)\begin{aligned} \min\quad&\sum_{e\in E}c_e x_e && (LP_3)\\ x_e&=\alpha_e^R+\beta_e^R &&\forall e\in\delta(R),\ \varnothing\ne R\subsetneq V\\ \alpha^R(\delta_S(R))&\geq p\lambda^R &&\forall\varnothing\ne R\subsetneq V\\ \beta^R(\delta(R))&\geq(p+q)(1-\lambda^R) &&\forall\varnothing\ne R\subsetneq V\\ 0\leq\alpha_e^R&\leq\lambda^R &&\forall e\in\delta(R),\ \varnothing\ne R\subsetneq V\\ 0\leq\beta_e^R&\leq1-\lambda^R &&\forall e\in\delta(R),\ \varnothing\ne R\subsetneq V\\ 0\leq\lambda^R&\leq1 &&\forall\varnothing\ne R\subsetneq V \tag*{(18)} \end{aligned}

By eliminating α\alpha and β\beta variables via Fourier-Motzkin elimination in a suitable order, we obtain the following LP that is equivalent to (LP3)(LP_3)—we do not show the Fourier-Motzkin derivation in the interests of brevity.

min⁡∑e∈Ecexe∑e∈δS(R)min⁡{xe,λR}≥pλR∀∅≠R⊊V∑e∈δU(R)min⁡{xe,1−λR}≥(p+q)(1−λR)∀∅≠R⊊V∑e∈δS(R)xe+∑e∈δU(R)min⁡{xe,1−λR}≥pλR+(p+q)(1−λR)∀∅≠R⊊V0≤xe≤1∀e∈E0≤λR≤1∀∅≠R⊊V(19)\begin{aligned} \min\quad&\sum_{e\in E} c_e x_e\\ \sum_{e\in\delta_S(R)} \min\{x_e,\lambda^R\} &\ge p\lambda^R &&\forall\varnothing\ne R\subsetneq V\\ \sum_{e\in\delta_U(R)} \min\{x_e,1-\lambda^R\} &\ge(p+q)(1-\lambda^R) &&\forall\varnothing\ne R\subsetneq V\\ \sum_{e\in\delta_S(R)}x_e+\sum_{e\in\delta_U(R)}\min\{x_e,1-\lambda^R\} &\ge p\lambda^R+(p+q)(1-\lambda^R) &&\forall\varnothing\ne R\subsetneq V\\ 0\le x_e&\le1 &&\forall e\in E\\ 0\le\lambda^R&\le1 &&\forall\varnothing\ne R\subsetneq V \tag*{(19)} \end{aligned}

Next, we eliminate the λ\lambda variables from (LP4)(LP_4) to arrive at the following LP:

min⁡∑e∈Ecexex(δS(R))+x(δU(R)−J)≥p∀J⊆δU(R):∣J∣≤qx(δS(R)−T)p−∣T∣+x(δS(R))+x(δU(R)−J)−pq−∣J∣≥1∀T⊆δS(R):∣T∣<p, ∀J⊆δU(R):∣J∣<q0≤xe≤1∀e∈E(20)\begin{aligned} \min\quad&\sum_{e\in E}c_ex_e\\ x(\delta_S(R))+x(\delta_U(R)-J)&\ge p &&\forall J\subseteq\delta_U(R): |J|\le q\\ \frac{x(\delta_S(R)-T)}{p-|T|}+\frac{x(\delta_S(R))+x(\delta_U(R)-J)-p}{q-|J|}&\ge1 &&\forall T\subseteq\delta_S(R): |T|<p,\ \forall J\subseteq\delta_U(R): |J|<q\\ 0\le x_e&\le1 &&\forall e\in E \tag*{(20)} \end{aligned}

We briefly outline why (LP4)(LP_4) and (LP5)(LP_5) are equivalent. If we have a feasible solution xx for (LP5)(LP_5), then the solution (x,(λR)∅≠R⊊V)(x,(\lambda^R)_{\varnothing\ne R\subsetneq V}) obtained by setting λR:=min⁡{aR,1−bR}\lambda^R:=\min\{a^R,1-b^R\} for each ∅≠R⊊V\varnothing\ne R\subsetneq V, where

aR:=min⁡T⊆δS(R):∣T∣<px(δS(R)∖T)p−∣T∣,bR:={q’th largest xe value among edges e∈δU(R)if ∣δU(R)∣≥q0otherwisea^R:=\min_{T\subseteq\delta_S(R):|T|<p}\frac{x(\delta_S(R)\setminus T)}{p-|T|}, \qquad b^R:=\begin{cases} q\text{’th largest }x_e\text{ value among edges }e\in\delta_U(R)&\text{if }|\delta_U(R)|\ge q\\ 0&\text{otherwise} \end{cases}

is feasible for (LP4)(LP_4). Moreover, if (x,(λR)∅≠R⊊V)(x,(\lambda^R)_{\varnothing\ne R\subsetneq V}) is a feasible solution for (LP4)(LP_4), then xx can be shown to satisfy the constraints of (LP5)(LP_5) 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 (LP5)(LP_5) can be solved in polynomial time via the Ellipsoid method since it admits a polynomial time separation oracle (even if pp and qq 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. (LP5)(LP_5) 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 (LP5)(LP_5), together with the second family restricted to T=J=∅T=J=\varnothing, 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 (LP1)(LP_1) has unbounded integrality gap.

Proposition 5.1. (LP1)(LP_1) has unbounded integrality gap on simple bipartite graphs.

Proof. We construct a simple bipartite instance to exhibit an unbounded integrality gap. Let p≥2p \ge2 and G=Kp+q,p+qG = K_{p+q,p+q} be the complete bipartite graph on p+qp+q vertices on both sides. Let the bipartition be V=L⊔RV = L \sqcup R. We assign the edges in GG to SS and UU as follows. Decompose GG into p+qp+q edge disjoint perfect matchings {M1,M2,…,Mp+q}\{M_1, M_2, \ldots, M_{p+q}\} (this is possible because GG is a complete bipartite graph with equal number of vertices on both sides). Let S=Mp+q∪⋃i=1p−1MiS = M_{p+q} \cup\bigcup_{i=1}^{p-1} M_i and U=⋃i∈{p,p+1,…,p+q−1}MiU = \bigcup_{i \in\{p,p+1,\ldots,p+q-1\}} M_i.

Define the cost function c:E→R≥0c : E \to\mathbb{R}_{\ge0} as

ce={ϵif e∈⋃i∈[p+q−1]Mi1otherwisec_e = \begin{cases} \epsilon& \text{if } e \in\bigcup_{i \in[p+q-1]} M_i \\ 1 & \text{otherwise} \end{cases}

Let FF be an optimal integral solution to this instance of Flex-Edge-Cover. Since ∣δ(v)∣=p+q|\delta(v)| = p+q and ∣δS(v)∣=p|\delta_S(v)| = p, F∩δ(v)F \cap\delta(v) must include the edge ev∈Mp+q∩δ(v)e_v \in M_{p+q} \cap\delta(v). Hence, c(F)≥∑v∈Vcev=p+qc(F) \ge\sum_{v \in V} c_{e_v} = p+q.

We now construct a feasible solution (x,λ)(x,\lambda) to LP1LP_1. Let λv=1p+q\lambda_v = \frac{1}{p+q} for all vertices v∈Vv \in V and let

xe={1if e∈⋃i∈[p+q−1]Mi0otherwise.x_e = \begin{cases} 1 & \text{if } e \in\bigcup_{i \in[p+q-1]} M_i \\ 0 & \text{otherwise.} \end{cases}

Then, 0≤x≤10 \le x \le1 and 0≤λ≤10 \le\lambda\le1. For every vertex v∈Vv \in V

x(δ(v))=p+q−1≥1=λv(p+q)x(\delta(v)) = p+q-1 \ge1 = \lambda_v(p+q)
x(δS(v))=p≥pp+q=λvp.x(\delta_S(v)) = p \ge\frac{p}{p+q} = \lambda_v p.

Thus (x,λ)(x,\lambda) is feasible for LP1LP_1 and the integrality gap is at least

c(F)∑e∈Ecexe≥p+qϵ(p+q)(p+q−1)=1ϵ(p+q−1)\frac{c(F)}{\sum_{e \in E} c_e x_e} \ge\frac{p+q}{\epsilon(p+q)(p+q-1)} = \frac{1}{\epsilon(p+q-1)}

which tends to ∞\infty as ϵ→0\epsilon\to0.

Tight example for the naive greedy heuristic

In this section, we investigate the naive greedy heuristic stated in the introduction: namely, for each vertex v∈Vv \in V, let Fv1F_v^1 be the cheapest p+qp+q edges incident to vv, Fv2F_v^2 be the cheapest pp safe edges incident to vv, and Fv=arg⁡min⁡{c(Fv1),c(Fv2)}F_v = \arg\min\{c(F_v^1), c(F_v^2)\}; return F=⋃v∈VFvF = \bigcup_{v \in V} F_v. We construct an instance to illustrate that 2-factor is the best possible for this heuristic.

Let p=1p = 1 and q=0q = 0. We construct a graph G=(V=L⊔R,E=S)G = (V = L \sqcup R, E = S) where L={ℓ1,ℓ2,…,ℓn}L = \{\ell_1,\ell_2,\ldots,\ell_n\}, R={r1,r2,…,rn}R = \{r_1,r_2,\ldots,r_n\}, E={ℓiri∣i∈[n]}∪{ℓir1∣i∈[n]∖{1}}E = \{\ell_i r_i \mid i \in[n]\} \cup\{\ell_i r_1 \mid i \in[n] \setminus\{1\}\}. Define a cost function c:E→R≥0c : E \to\mathbb{R}_{\ge0} where cℓiri=1+ϵc_{\ell_i r_i} = 1+\epsilon for every i≥1i \ge1 and cℓir1=1c_{\ell_i r_1} = 1 for every i≥2i \ge2. For ϵ\epsilon sufficiently small, the optimal solution F∗F^* is F∗={ℓiri∣i∈[n]}F^* = \{\ell_i r_i \mid i \in[n]\} with c(F∗)=n(1+ϵ)c(F^*) = n(1+\epsilon). We can adversarially set the processing order of the vertices to be LL first and then RR. Then, the algorithm will construct the solution F=EF = E. We have that

c(F)c(F∗)=n(1+ϵ)+n−1n(1+ϵ)=1+n−1n(1+ϵ).\frac{c(F)}{c(F^*)} = \frac{n(1+\epsilon)+n-1}{n(1+\epsilon)} = 1+\frac{n-1}{n(1+\epsilon)}.

As n→∞n \to\infty and ϵ→0\epsilon\to0, this ratio approaches 2. We note that this example is a simple graph.

References

  1. [1]D. Adjiashvili, F. Hommelsheim, and M. Mühlenthaler. Flexible graph connectivity. Mathematical Programming, 192:409–441, 2022.
  2. [2]D. Adjiashvili, S. Stiller, and R. Zenklusen. Bulk-robust combinatorial optimization. Mathematical Programming, 149(1-2):361–390, 2015.DOI
  3. [3]A. Armon and U. Zwick. Multicriterial global minimum cuts. Algorithmica, 46(1):15–26, 2006.
  4. [4]A. Atamtürk. Strong formulations of robust mixed 0–1 programming. Mathematical Programming, 108(2):235–250, 2006.DOI
  5. [5]E. Balas. Disjunctive programming. Annals of Discrete Mathematics, 5:3–51, 1979.
  6. [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. [7]I. Bansal. A global analysis of the primal-dual method for edge augmentation problems. In Integer Programming and Combinatorial Optimization, 2025.DOI
  8. [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. [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. [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. [11]D. Bienstock. Approximate formulations for 0-1 knapsack sets. Operations Research Letters, 36(3):317–320, 2008.DOI
  12. [12]D. Bienstock and B. McClosky. Tightening simple mixed-integer sets with guaranteed bounds. Mathematical Programming, 133:337–363, 2012.
  13. [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. [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. [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. [16]S. Boyd, J. Cheriyan, A. Haddadan, and S. Ibrahimपुर. Approximation algorithms for flexible graph connectivity. Mathematical Programming, 204:493–516, 2024.
  17. [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. [18]C. Chekuri and R. Jain. Approximation algorithms for network design in non-uniform fault models. Mathematical Programming, Series A, October 2025.
  19. [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. [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. [21]M. Conforti and L. A. Wolsey. Compact formulations as a union of polyhedra. Mathematical Programming, 114(2):277–289, 2008.DOI
  22. [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. [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. [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. [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. [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. [27]G. Kortsarz, Z. Nutov, and E. Shalom. Approximating activation edge-cover and facility location problems. Theoretical Computer Science, 930:218–228, 2022.
  28. [28]A. N. Letchford. On disjunctive cuts for combinatorial optimization. Journal of Combinatorial Optimization, 5(3):299–315, 2001.
  29. [29]D. Pritchard. An LP with Integrality Gap 1 + ϵ for Multidimensional Knapsack. arXiv preprint arXiv: 1005.3324, 2010.arxiv.org/abs/1005.3324
  30. [30]D. Pritchard and D. Chakrabarty. Approximability of sparse integer programs. Algorithmica, 61(1):75–93, 2011.
  31. [31]A. Schrijver. Theory of linear and integer programming. John Wiley & Sons, 1998.
  32. [32]A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003.
  33. [33]R. Zenklusen. Connectivity interdiction. Operations Research Letters, 42(6):450–454, 2014.DOI
  34. [34]M. Zuckerberg. A Set Theoretic Approach to Lifting Procedures for 0,1 Integer Programming. PhD thesis, Columbia University, 2004.

Paper details

vlnc:W_7t8g6346
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

AI-tools

View statement
Looking for related papers…
Contents