when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-155206
URL:

; ; ;

### Approximation Algorithms for Flexible Graph Connectivity

 pdf-format:

### Abstract

We present approximation algorithms for several network design problems in the model of Flexible Graph Connectivity (Adjiashvili, Hommelsheim and Mühlenthaler, "Flexible Graph Connectivity", Math. Program. pp. 1-33 (2021), IPCO 2020: pp. 13-26). In an instance of the Flexible Graph Connectivity (FGC) problem, we have an undirected connected graph G = (V,E), a partition of E into a set of safe edges S and a set of unsafe edges U, and nonnegative costs {c_e}_{e ∈ E} on the edges. A subset F ⊆ E of edges is feasible for FGC if for any unsafe edge e ∈ F ∩ U, the subgraph (V,F⧵{e}) is connected. The algorithmic goal is to find a (feasible) solution F that minimizes c(F) = ∑_{e ∈ F} c_e. We present a simple 2-approximation algorithm for FGC via a reduction to the minimum-cost r-out 2-arborescence problem. This improves upon the 2.527-approximation algorithm of Adjiashvili et al.
For integers p ≥ 1 and q ≥ 0, the (p,q)-FGC problem is a generalization of FGC where we seek a minimum-cost subgraph H = (V,F) that remains p-edge connected against the failure of any set of at most q unsafe edges; that is, for any set F' ⊆ U with |F'| ≤ q, H-F' = (V, F ⧵ F') should be p-edge connected. Note that FGC corresponds to the (1,1)-FGC problem. We give approximation algorithms for two important special cases of (p,q)-FGC: (a) Our 2-approximation algorithm for FGC extends to a (k+1)-approximation algorithm for the (1,k)-FGC problem. (b) We present a 4-approximation algorithm for the (k,1)-FGC problem.
For the unweighted FGC problem, where each edge has unit cost, we give a 16/11-approximation algorithm. This improves on the result of Adjiashvili et al. for this problem.
The (p,q)-FGC model with p = 1 or q ≤ 1 can be cast as the Capacitated k-Connected Subgraph problem which is a special case of the well-known Capacitated Network Design problem. We denote the former problem by Cap-k-ECSS. An instance of this problem consists of an undirected graph G = (V,E), nonnegative integer edge-capacities {u_e}_{e ∈ E}, nonnegative edge-costs {c_e}_{e ∈ E}, and a positive integer k. The goal is to find a minimum-cost edge-set F ⊆ E such that every (non-trivial) cut of the capacitated subgraph H(V,F,u) has capacity at least k. We give a min(k, 2max_{e ∈ E} u_e)-approximation algorithm for this problem.

### BibTeX - Entry

```@InProceedings{boyd_et_al:LIPIcs.FSTTCS.2021.9,
author =	{Boyd, Sylvia and Cheriyan, Joseph and Haddadan, Arash and Ibrahimpur, Sharat},
title =	{{Approximation Algorithms for Flexible Graph Connectivity}},
booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
pages =	{9:1--9:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-215-0},
ISSN =	{1868-8969},
year =	{2021},
volume =	{213},
editor =	{Boja\'{n}czy, Miko{\l}aj and Chekuri, Chandra},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},