在网络设计中，边的失效往往不是均匀的。为此我们提出了 多层灵活图连通性（k‑tier Flexible Graph Connectivity，k‑tier FGC）模型。模型的输入是一张无向图 $G=(V,E)$，每条边都有非负费用，并且边被划分为 $k$ 层嵌套集合 $T_1\subseteq T_2\subseteq\dots\subseteq T_k=E$，每层都有整数需求 $q_i$（其中 $q_1\leq q_i$）。目标是选取最小费用的边集 $F\subseteq E$，使得子图 $(V,F)$ 不存在 不安全割——即任意割的跨割边数在对应层的需求 $q_i$ 之上。 当 $k=1$ 时，该问题退化为最小费用 $p$‑边连通生成子图问题，已知为 APX‑hard。
我们针对固定常数 $k$ 的三种变体给出了近似算法：
- 一般的 k‑tier FGC：基于线性规划的对数近似算法；
- 最小基数 k‑tier FGC：构造性组合近似，近似比仅依赖于最小层需求 $q_1$ 与最高层需求 $q_k$；
- k‑tier 灵活多图连通性：允许对同一条边选取多份拷贝，每份拷贝均需支付该边费用，提供基于 LP 的 2‑近似。
这些结果表明，即使在存在层次化可靠性要求的情况下，也能在多项式时间内获得可观的近似解。
博主点评：该工作将传统的连通性问题推广到更细粒度的可靠性模型，算法设计兼顾理论深度与实际可行性，为网络鲁棒性设计提供了新思路。