Protecting the Connectivity of a Graph Under Nonuniform Edge Failures
SIAM Journal on Discrete Mathematics · 30.09.2026 · 40 (3) · 1141-1167
DOI: 10.1137/25m1767819 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 23.07.2026. Verfasst von Felix Hommelsheim und 3 weiteren Autor:innen. Die Arbeit nennt 52 Literaturangaben. Gefördert von: National Natural Science Foundation of China.
Abstract (Originalsprache)
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 nonuniform failure model. We introduce the [Formula: see text]-Steiner-Connectivity Preservation problem where we protect a minimum-cost set of edges such that the underlying graph maintains [Formula: see text]-edge-connectivity between given terminal pairs against edge failures, assuming at most [Formula: see text] unprotected edges can fail. We design polynomial-time exact algorithms for the cases where [Formula: see text] and [Formula: see text] are small and approximation algorithms for general values of [Formula: see text] and [Formula: see text]. Additionally, we show that when both [Formula: see text] and [Formula: see text] are part of the input, even deciding whether a given solution is feasible is [Formula: see text]-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 [Formula: see text] or [Formula: see text] is constant, for which our new hardness result now provides justification.
Förderung
- National Natural Science Foundation of China
Zitieren
APA
Hommelsheim, F., Liu, Z., Megow, N., & Zhang, G. (2026). Protecting the Connectivity of a Graph Under Nonuniform Edge Failures. SIAM Journal on Discrete Mathematics, 40(3), 1141-1167. https://doi.org/10.1137/25m1767819
Vancouver
Hommelsheim F, Liu Z, Megow N, Zhang G. Protecting the Connectivity of a Graph Under Nonuniform Edge Failures. SIAM Journal on Discrete Mathematics. 2026;40(3):1141-1167. doi:10.1137/25m1767819
BibTeX
@article{Hommelsheim2026,
author = {Hommelsheim, Felix and Liu, Zhenwei and Megow, Nicole and Zhang, Guochuan},
title = {Protecting the Connectivity of a Graph Under Nonuniform Edge Failures},
journal = {SIAM Journal on Discrete Mathematics},
year = {2026},
volume = {40},
number = {3},
pages = {1141--1167},
doi = {10.1137/25m1767819}
}
EUVIMED