Approximation Algorithms for Flexible Graph Connectivity

Network design and graph connectivity are core topics in Theoretical Computer Science and Operations Research. A basic problem in network design is to find a minimum-cost sub-network $H$ of a given network $G$ such that $H$ satisfies some specified connectivity requirements. Most of these problems are NP-hard. Several important algorithmic paradigms were developed in the context of these topics, ranging from exact algorithms for the shortest ${s,t}$-path problem and the minimum spanning tree ($\mathrm{MST}$) problem to linear programming-based approximation algorithms for the survivable network design problem and the generalized Steiner network problem. Network design problems are often motivated by practical considerations such as the design of fault-tolerant supply chains, congestion control for urban road traffic, and the modeling of epidemics (see [13, 15, 18]).

Recently, Adjiashvili, Hommelsheim and Mühlenthaler [1, 2] introduced a new model called Flexible Graph Connectivity ($\mathrm{FGC}$), that is motivated by research in robust optimization. (In this paper, the notation $\mathrm{FGC}$ may be used as an abbreviation for “the $\mathrm{FGC}$ problem”; we use similar abbreviations for the names of other related problems.) In an instance of $\mathrm{FGC}$, we have an undirected connected graph $G=(V,E)$, a partition of $E$ into a set of safe edges $\mathscr{S}$ and a set of unsafe edges $\mathscr{U}$, and nonnegative costs $c:E\to\mathbb{R}_{\geq 0}$ on the edges. The graph $G$ may have multiedges, but no self-loops. We use $n$ to denote the number of vertices of $G$. The cost of an edge-set $F\subseteq{E}$ is denoted by $c(F)=\sum_{e\in{F}}c_{e}$. A subset $F\subseteq E$ of edges is feasible for $\mathrm{FGC}$ if for any unsafe edge $e\in F\cap\mathscr{U}$, the subgraph $(V,F\setminus\{e\})$ is connected. The problem is to find a feasible edge-set $F$ of minimum cost. The motivation for studying $\mathrm{FGC}$ is two-fold. First, $\mathrm{FGC}$ generalizes many well-studied survivable network design problems. Notably, the problem of finding a minimum-cost $2$-edge connected spanning subgraph (abbreviated as $2\text{-}\mathrm{ECSS}$) corresponds to the special case of $\mathrm{FGC}$ where all edges are unsafe, and the $\mathrm{MST}$ problem corresponds to the special case of $\mathrm{FGC}$ where all edges are safe. Second, $\mathrm{FGC}$ captures a non-uniform model of survivable network design problems where a specified subset of edges never fail, whereas each edge can fail in the classical model of survivable network design problems. Since $\mathrm{FGC}$ generalizes the minimum-cost $2\text{-}\mathrm{ECSS}$ problem, it is APX-hard (see [7]); thus, a polynomial-time approximation scheme for $\mathrm{FGC}$ is ruled out unless P$=$NP.

The notion of $(p,q)\text{-}\mathrm{FGC}$ is an extension of the basic $\mathrm{FGC}$ model where we have two additional integer parameters $p$ and $q$ satisfying $p\geq 1$ and $q\geq 0$. For a subgraph $H=(V,F)$ of $G$ and a vertex-set $S\subseteq{V}$, we use $\delta_{H}(S)$ to denote the set of edges in $H$ with exactly one end-vertex in $S$. A subset $F\subseteq E$ of edges is feasible for $(p,q)\text{-}\mathrm{FGC}$ if the spanning subgraph $H=(V,F)$ is $p$-edge connected, and moreover, the deletion of any set of at most $q$ unsafe edges of $F$ preserves $p$-edge connectivity. In other words, each cut $\delta_{H}(S)$, $\emptyset\neq{S}\subsetneq{V}$, of $H$ either contains $p$ safe edges or contains $p+q$ (safe or unsafe) edges. The algorithmic goal is to find a feasible edge-set $F$ of minimum cost. The $(p,q)\text{-}\mathrm{FGC}$ problem is a natural and fundamental question in robust network design. Note that the $\mathrm{FGC}$ problem is the same as the $(1,1)\text{-}\mathrm{FGC}$ problem. Observe that the problem of finding a minimum-cost $p$-edge connected spanning subgraph (abbreviated as $p\text{-}\mathrm{ECSS}$) corresponds to the special case of $(p,q)\text{-}\mathrm{FGC}$ where all edges are safe, and the problem of finding a minimum-cost $(p+q)\text{-}\mathrm{ECSS}$ corresponds to the special case of $(p,q)\text{-}\mathrm{FGC}$ where all edges are unsafe. Informally speaking, the model of $(p,q)\text{-}\mathrm{FGC}$ interpolates between $p$-edge connectivity (when all edges are safe) and $(p+q)$-edge connectivity (when all edges are unsafe).

For each of the problems considered in this paper, any solution (i.e., output) must be a subgraph of the graph $G$ of the instance; that is, the (multi) set of edges $F$ of a solution must be a subset of the (multi) set $E(G)$; in other words, the number of copies of an edge $e=vw$ in $F$ cannot exceed the number of copies of $e$ in $E(G)$; see the discussion in [16, Chapter 3.1].

The $(p,q)\text{-}\mathrm{FGC}$ model is related to the model of Capacitated Network Design. There are several results pertaining to approximation algorithms for various problems in Capacitated Network Design; for example, see Goemans et al. [8] and Chakrabarty et al. [3]. Let $k$ be a positive integer. The Capacitated $k$-Connected Subgraph problem, see [3], is a well studied problem in this area. We denote this problem by $\mathrm{Cap}\text{-}k\text{-}\mathrm{ECSS}$. In an instance of this problem, we have an undirected connected graph $G=(V,E)$, nonnegative integer edge-capacities $u:E\to\mathbb{Z}_{\geq 0}$, nonnegative edge-costs $c:E\to\mathbb{R}_{\geq 0}$, and a positive integer $k$. The goal is to find an edge-set $F\subseteq E$ such that for any nonempty $R\subsetneq{V}$ we have $\sum_{e\in\delta_{G}(R)\cap F}u_{e}\geq k$, and $c(F)$ is minimized. Let $n$ and $m$ denote the number of vertices and edges of $G$, respectively. For this problem, Goemans et al. [8] give a $\min(2k,m)$-approximation algorithm, and Chakrabarty et al. [3] give a randomized $O(\log n)$-approximation algorithm. We mention that for some particular values of $p$ and $q$, such as $p=1$ (and arbitrary $q$) or $q\leq 1$ (and arbitrary $p$), $(p,q)\text{-}\mathrm{FGC}$ can be cast as a special case of the $\mathrm{Cap}\text{-}k\text{-}\mathrm{ECSS}$ problem. The $\mathrm{FGC}$ problem corresponds to the $\mathrm{Cap}\text{-}2\text{-}\mathrm{ECSS}$ problem where safe edges have capacity two and unsafe edges have capacity one. Moreover, $(1,k)\text{-}\mathrm{FGC}$ corresponds to the $\mathrm{Cap}\text{-}(k+1)\text{-}\mathrm{ECSS}$ problem where safe edges have capacity $k+1$ and unsafe edges have capacity one; $(k,1)\text{-}\mathrm{FGC}$ corresponds to the $\mathrm{Cap}\text{-}(k(k+1))\text{-}\mathrm{ECSS}$ problem where safe edges have capacity $k+1$ and unsafe edges have capacity $k$. We mention that there exist values of $p$ and $q$ (e.g., $p=2,q=2$) such that the $(p,q)\text{-}\mathrm{FGC}$ problem differs from the $\mathrm{Cap}\text{-}(p(p+q))\text{-}\mathrm{ECSS}$ problem where safe edges have capacity $p+q$ and unsafe edges have capacity $p$.

We give a $(k+1)$-approximation for $(1,k)\text{-}\mathrm{FGC}$, where $k$ is a positive integer. The $2$-approximation for $\mathrm{FGC}$ (Theorem 1.1) follows as a special case. Recall that in an instance of $(1,k)\text{-}\mathrm{FGC}$ we have an undirected graph $G=(V,E)$ (with no self loops), a partition of $E$ into safe and unsafe edges, $E=\mathscr{S}\,\dot{\cup}\,\mathscr{U}$, and nonnegative edge-costs $c:E\to\mathbb{R}_{\geq 0}$. Our objective is to find a minimum-cost edge-set $F\subseteq E$ such that the subgraph $(V,F)$ remains connected against the failure of any set of $k$ unsafe edges.

For a subgraph $H$ of $G$ and a vertex-set $S\subseteq{V}$, we use $\delta_{H}(S)$ or $\delta_{E(H)}(S)$ to denote the set of edges in $H$ with exactly one end-vertex in $S$, i.e., $\delta_{H}(S):=\{e=uv\in E(H):|\{u,v\}\cap S|=1\}$. We drop the subscript when the underlying graph is clear from the context.

The following characterization of feasible solutions of $(1,k)\text{-}\mathrm{FGC}$ is straightforward.

We check the feasibility of $F$ for $(1,k)\text{-}\mathrm{FGC}$ by creating an auxiliary capacitated graph that has a capacity of $k+1$ for each safe edge and a capacity of one for each unsafe edge; then, we test whether or not the minimum capacity of a cut of the auxiliary graph is at least $k+1$. For the rest of this section, we assume that the given instance of $(1,k)\text{-}\mathrm{FGC}$ is feasible.

As mentioned before, our algorithm for $(1,k)\text{-}\mathrm{FGC}$ is based on a reduction to the minimum-cost rooted $(k+1)$-arborescence problem. We state a few standard results on arborescences. Let $D=(W,A)$ be a digraph and let $c^{\prime}:A\to\mathbb{R}_{\geq 0}$ be nonnegative costs on the arcs. We remark that $D$ may have parallel arcs but it has no self-loops. Let $r\in W$ be a designated root vertex. For a subgraph $H$ of $D$ and a nonempty vertex-set $S\subsetneq W$, we use $\delta^{\mathrm{in}}_{H}(S)$ to denote the set of arcs in $H$ such that the head of the arc is in $S$ and the tail of the arc is in $W\setminus S$, i.e., $\delta^{\mathrm{in}}_{H}(S):=\{a=(u,v)\in A(H):u\notin S,v\in S\}$.

In other words, an $r$-rooted arborescence is a directed spanning tree such that vertex $r$ has no incoming arcs and every other vertex has one incoming arc. An $r$-rooted $k$-arborescence is a union of $k$ arc-disjoint $r$-rooted arborescences.

The following results on rooted arborescences and the corresponding optimization problem are useful for us.

Informally speaking, our proofs map undirected graphs to their directed counterparts by bidirecting edges. We formalize this notion.

The following lemma shows how a solution $F$ to $(1,k)\text{-}\mathrm{FGC}$ can be used to obtain a rooted $(k+1)$-arborescence (in an appropriate digraph) of cost at most $(k+1)$ times $c(F)$.

Lemma 2.5 naturally suggests a reduction from $(1,k)\text{-}\mathrm{FGC}$ to the minimum-cost $r$-rooted $(k+1)$-arborescence problem. We prove the main theorem of this section.

In this section we consider the $\mathrm{Cap}\text{-}k\text{-}\mathrm{ECSS}$ problem. We are given a graph $G=(V,E)$, nonnegative integer edge-capacities $u:E\to\mathbb{Z}_{\geq 0}$, nonnegative edge-costs $c:E\to\mathbb{R}_{\geq 0}$, and a positive integer $k$. Our goal is to find a spanning subgraph $H=(V,F)$ such that for all nonempty sets $R\subsetneq V$ we have $u(\delta_{F}(R))\geq k$, and the cost $c(F)$ is minimized.

Given an instance of the $\mathrm{Cap}\text{-}k\text{-}\mathrm{ECSS}$ problem, we may assume without loss of generality that $u_{e}\in\{1,\dots,k\}$ for all $e\in E$ (we can drop edges with zero capacity and replace edge-capacities $\geq{k+1}$ by $k$). We also assume that the $\mathrm{Cap}\text{-}k\text{-}\mathrm{ECSS}$ instance is feasible. This can be verified in polynomial time by checking if $G$ has any cut $\delta(S)$, $\emptyset\neq{S}\subsetneq{V}$, with capacity $u(\delta(S))$ less than $k$. Let ${u}_{\mathrm{max}}=\max_{e\in E}u_{e}$ denote the maximum capacity of an edge in $G$. Our main result in this section is a $\min(k,2{u}_{\mathrm{max}})$-approximation algorithm for the $\mathrm{Cap}\text{-}k\text{-}\mathrm{ECSS}$ problem (Theorem 1.3); our algorithm is based on a reduction to the minimum-cost rooted $k$-arborescence problem.

Our main result in this section is a $4$-approximation algorithm for $(k,1)\text{-}\mathrm{FGC}$ (Theorem 1.4). Recall that in an instance of $(k,1)\text{-}\mathrm{FGC}$, we have a graph $G=(V,E)$, with a partition of the edge-set into safe and unsafe edges, $E=\mathscr{S}\cup\mathscr{U}$, nonnegative edge-costs $c:E\to\mathbb{R}_{\geq 0}$, and a positive integer $k$. The objective is to find a minimum-cost subgraph that remains $k$-edge connected against the failure of any one unsafe edge. We remark that for the $k=1$ case, Theorem 1.1 yields a better approximation factor than Theorem 1.4. Let $F^{*}$ denote an optimal solution to the $(k,1)\text{-}\mathrm{FGC}$ instance. The following result pertains to feasible solutions of $(k,1)\text{-}\mathrm{FGC}$.

For the rest of this section, we assume that the given instance of $(k,1)\text{-}\mathrm{FGC}$ is feasible.

Proposition 4.1 suggests a two-stage strategy for finding an approximately optimal solution to $(k,1)\text{-}\mathrm{FGC}$. In the first stage, we do not distinguish between safe edges and unsafe edges, and we compute a cheap $k\text{-}\mathrm{ECSS}$ of $G=(V,E)$ that we denote by $H_{1}=(V,F_{1})$. Clearly, for every nonempty set $S\subsetneq V$, we have $|\delta_{H_{1}}(S)|\geq{k}$; if equality holds, then we call $\delta_{H_{1}}(S)$ a $k$-edge-cut. If $F_{1}$ is feasible for $(k,1)\text{-}\mathrm{FGC}$, then we are done. Otherwise, by Proposition 4.1, the infeasibility of $F_{1}$ for $(k,1)\text{-}\mathrm{FGC}$ is due to $k$-edge-cuts of $H_{1}$ that contain at least one unsafe edge. We call such cuts deficient. In the second stage, we address the remaining augmentation problem for the deficient cuts, by casting it as a special case of the minimum-cost $f$-connectivity problem (defined below).

An instance of the minimum-cost $f$-connectivity problem consists of an undirected graph $G^{\prime}=(V^{\prime},E^{\prime})$, nonnegative edge-costs $c^{\prime}:E^{\prime}\to\mathbb{R}_{\geq 0}$, and a requirement function $f:2^{V^{\prime}}\to\{0,1\}$ satisfying $f(\emptyset)=f(V)=0$. We assume access to $f$ via a value oracle that takes as input a vertex-set $S\subseteq V$ and outputs $f(S)$. An edge-set $F\subseteq E^{\prime}$ is feasible if $|F\cap\delta_{G^{\prime}}(S)|\geq f(S)$ for every $S\subseteq V^{\prime}$. In other words, $F$ is feasible if and only if for every vertex-set $S$ with $f(S)=1$ there is at least one $F$-edge in the cut $\delta(S)$. The objective is to find a feasible $F\subseteq E^{\prime}$ that minimizes $c^{\prime}(F)$. The minimum-cost $f$-connectivity problem can be formulated as an integer program whose linear relaxation (P) is stated below. For each edge $e\in E^{\prime}$, the LP (linear program) has a nonnegative variable $x_{e}$; informally speaking, $x_{e}$ quantifies the “usage” of the edge $e$ in a feasible solution to the LP.

The minimum-cost $f$-connectivity problem has received attention since it captures many well-known problems in network design. In particular, it captures the generalized Steiner network problem. Williamson et al. [20] gave a primal-dual framework to obtain approximation algorithms for the minimum-cost $f$-connectivity problem when $f$ is a proper function, and more generally, when $f$ is an uncrossable function (also see the book chapter by Goemans and Williamson [9]).

Under the assumption that minimal violated sets can be computed efficiently throughout, the primal-dual algorithm of [20] gives a $2$-approximation for the minimum-cost $f$-connectivity problem with an uncrossable function $f$. There is no explicit result in [20] that can be quoted verbatim and applied for our purposes, so we state the most relevant result from [20].

We now describe a two-stage algorithm that produces a $4$-approximate $(k,1)\text{-}\mathrm{FGC}$ solution in polynomial time, thereby proving Theorem 1.4.