Multi-tier Flexible Graph Connectivity
Data Structures and Algorithms
Summary
The authors study a problem where a network's edges are grouped into multiple levels (tiers), each with different requirements for safety against failures. They want to find the cheapest set of edges ensuring that every group of nodes remains safely connected according to at least one tier's criteria. They provide algorithms that give approximate solutions for this problem in three settings, including one where multiple copies of edges can be used. Their work extends known results from simpler single-tier cases to more complex multi-tier situations.
graph connectivityedge failuresapproximation algorithmstiered networksedge costssafe cutslinear programming (LP)multi-graph connectivityp-edge-connected subgraphcombinatorial algorithms
Authors
Karthekeyan Chandrasekaran, Raymond Jiang, Krishna Kalathur
Abstract
Motivated by non-uniform edge failures in network design, we introduce a multi-tier model of flexible graph connectivity. In k-tier Flexible Graph Connectivity (k-tier FGC), the input is an undirected graph G=(V, E) with non-negative edge costs, along with a classification of the edges into nested tiers T_1 subseteq T_2 subseteq ... subseteq T_k = E and non-negative integral tier requirements q_1 <= q_2 <= ... <= q_k. A non-empty proper subset R of vertices is safe if it is safe along one of the tiers, i.e., there exists i in [k] such that |delta(R) cap T_i| >= q_i. The goal is to find a minimum cost subset F subseteq E of edges such that the subgraph (V, F) has no unsafe cuts. The case of k=1 corresponds to the min-cost p-edge-connected spanning subgraph problem which is APX-hard. We design approximation algorithms for every fixed constant k for three variants of k-tier FGC: (i) for k-tier FGC, we design an LP-based logarithmic approximation, (ii) for min-cardinality k-tier FGC, we design a combinatorial approximation whose factor depends only on the tier requirements q_1 and q_k, and (iii) for k-tier Flexible Multi-Graph Connectivity, where we are allowed to use multiple copies of each edge while paying the cost of the edge for each chosen copy of the edge, we design an LP-based 2-approximation.