Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures
Authors:
- Felix HommelsheimFHFelix Hommelsheim
- Zhenwei LiuZLZhenwei Liu
- Nicole MegowNMNicole Megow
- Guochuan ZhangGZGuochuan Zhang
Preprint
Abstract
We study the problem of guaranteeing the connectivity of a given graph by protecting or strengthening edges. Herein, a protected edge is assumed to be robust and will not fail, which features a non-uniform failure model. We introduce the $(p,q)$-Steiner-Connectivity Preservation problem where we protect a minimum-cost set of edges such that the underlying graph maintains $p$-edge-connectivity between given terminal pairs against edge failures, assuming at most $q$ unprotected edges can fail. We design polynomial-time exact algorithms for the cases where $p$ and $q$ are small and approximation algorithms for general values of $p$ and $q$. Additionally, we show that when both $p$ and $q$ are part of the input, even deciding whether a given solution is feasible is NP-complete. This hardness also carries over to Flexible Network Design, a research direction that has gained significant attention. In particular, previous work focuses on problem settings where either $p$ or $q$ is constant, for which our new hardness result now provides justification.
Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Approximation algorithms for network design in non-uniform fault modelsMathematical Programming, 2025
- Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable FunctionsAlgorithmica, 2024
- Approximation algorithms for flexible graph connectivityMathematical Programming, 2023
- A Better-Than-2 Approximation for Weighted Tree Augmentation2022
- The parameterized complexity of the minimum shared edges problemJournal of Computer and System Sciences, 2019
- Approximability of Capacitated Network DesignAlgorithmica, 2014
- A Factor 2 Approximation Algorithm for the Generalized Steiner Network ProblemCombinatorica, 2001
- Primal-dual approximation algorithms for integral flow and multicut in treesAlgorithmica, 1997
- A primal-dual approximation algorithm for generalized steiner network problemsCombinatorica, 1995
- The Steiner problem with edge lengths 1 and 2Information Processing Letters, 1989