An O(log n)-approximation algorithm for (p,q)-flexible graph connectivity via independent rounding
Mathematical Programming · 22.07.2026
DOI: 10.1007/s10107-026-02387-5 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematical Programming, online erschienen am 22.07.2026. Verfasst von Sharat Ibrahimpur und 1 weiteren Autor:innen. Die Arbeit nennt 25 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Deutsche Forschungsgemeinschaft.
Abstract (Originalsprache)
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)$$ O ( log n ) -approximation algorithm based on independent rounding, improving the previous best approximation ratio of $$O(q \log n)$$ O ( q log n ) . 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)$$ Θ ( log n ) 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.
Förderung
- Deutsche Forschungsgemeinschaft
Zitieren
APA
Ibrahimpur, S., & Végh, L. A. (2026). An O(log n)-approximation algorithm for (p,q)-flexible graph connectivity via independent rounding. Mathematical Programming. https://doi.org/10.1007/s10107-026-02387-5
Vancouver
Ibrahimpur S, Végh LA. An O(log n)-approximation algorithm for (p,q)-flexible graph connectivity via independent rounding. Mathematical Programming. 2026. doi:10.1007/s10107-026-02387-5
BibTeX
@article{Ibrahimpur2026,
author = {Ibrahimpur, Sharat and Végh, László A.},
title = {An O(log n)-approximation algorithm for (p,q)-flexible graph connectivity via independent rounding},
journal = {Mathematical Programming},
year = {2026},
doi = {10.1007/s10107-026-02387-5}
}
EUVIMED