In network design, edge failures are often non‑uniform. To capture this, we introduce the multi‑tier Flexible Graph Connectivity (k‑tier Flexible Graph Connectivity, k‑tier FGC) model. The input is an undirected graph $G=(V,E)$ with non‑negative edge costs, together with a nesting of edge sets $T_1\subseteq T_2\subseteq\cdots\subseteq T_k=E$ and integer tier requirements $q_i$ (with $q_1\le q_i$). The goal is to select a minimum‑cost edge subset $F\subseteq E$ such that the subgraph $(V,F)$ has no unsafe cuts—i.e., every cut crosses at least $q_i$ edges from tier $T_i$. When $k=1$ the problem reduces to the min‑cost $p$‑edge‑connected spanning subgraph problem, known to be APX‑hard.
We give approximation algorithms for any fixed constant $k$ for three variants:
- General k‑tier FGC: an LP‑based logarithmic‑approximation;
- Minimum‑cardinality k‑tier FGC: a combinatorial approximation whose ratio depends only on $q_1$ and $q_k$;
- k‑tier Flexible Multi‑Graph Connectivity: multiple copies of an edge may be bought, each at the edge’s cost; we obtain an LP‑based 2‑approximation.
These results show that even with hierarchical reliability requirements, polynomial‑time algorithms can achieve meaningful approximations.
Blogger's Review: The paper extends classic connectivity problems to a finer‑grained reliability framework and provides algorithms that balance theoretical guarantees with practical relevance, offering valuable insights for robust network design.