An O(log n)-approximation algorithm for (p,q)-flexible graph connectivity via independent rounding
针对(p,q)柔性图连通性，提出一种O(log n)近似算法，改进了此前O(q log n)的界。算法用独立取整和新的线性规划，并扩展到多个安全层级，适合研究图连通性近似算法的学者。
Abstract In the Flexible Graph Connectivity (FGC) problem, we are given an undirected multigraph on n vertices with nonnegative edge costs, where each edge is classified as either safe or unsafe . Given integer parameters p and q , the goal in ( p , q )-FGC is to purchase a minimum-cost set of edges such that the resulting spanning subgraph remains p -edge-connected after the removal of any set of up to q unsafe edges. Our main contribution is an $$O(\log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -approximation algorithm based on independent rounding, improving the previous best approximation ratio of $$O(q \log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>q</mml:mi> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . Central to our approach is a new linear programming formulation of feasible solutions that encodes knapsack cover inequalities as cut-capacity constraints. Unlike prior work, the capacity of an edge in a cut may depend on the partially purchased solution for this cut. We show that the resulting linear program admits a polynomial-time separation oracle. Scaling the fractional solution by $$\varTheta (\log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Θ</mml:mi> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and applying independent rounding yields a feasible integral solution with constant probability; here, we leverage the knapsack cover inequalities to obtain strong concentration bounds for the rounded solution relative to any given partial solution. A key ingredient in both separation and rounding is the use of Karger’s bound on the number of near-minimum cuts. We also extend the ( p , q )-FGC problem to model more than two safety tiers and show that our results and techniques extend naturally to this setting, albeit with increased approximation ratios and running times that scale with the number of tiers.