License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2021.9
URN: urn:nbn:de:0030-drops-155206
URL: https://drops.dagstuhl.de/opus/volltexte/2021/15520/
Go to the corresponding LIPIcs Volume Portal


Boyd, Sylvia ; Cheriyan, Joseph ; Haddadan, Arash ; Ibrahimpur, Sharat

Approximation Algorithms for Flexible Graph Connectivity

pdf-format:
LIPIcs-FSTTCS-2021-9.pdf (0.7 MB)


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},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15520},
  URN =		{urn:nbn:de:0030-drops-155206},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.9},
  annote =	{Keywords: Approximation Algorithms, Combinatorial Optimization, Network Design, Edge-Connectivity of Graphs, Reliability of Networks}
}

Keywords: Approximation Algorithms, Combinatorial Optimization, Network Design, Edge-Connectivity of Graphs, Reliability of Networks
Collection: 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Issue Date: 2021
Date of publication: 29.11.2021


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI