2026-07-21T10:22:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22876 2025-10-02T13:36:12Z ddc:004 open_access

Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures Hommelsheim, Felix Liu, Zhenwei Megow, Nicole Zhang, Guochuan Network Design Edge Failures Graph Connectivity Approximation Algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Felix Hommelsheim and Zhenwei Liu and Nicole Megow and Guochuan Zhang 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.51 urn:nbn:de:0030-drops-228761 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.51 eng https://creativecommons.org/licenses/by/4.0/legalcode