Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913641314385920 |
|---|---|
| author | Hommelsheim, Felix Liu, Zhenwei Megow, Nicole Zhang, Guochuan |
| author_facet | Hommelsheim, Felix Liu, Zhenwei Megow, Nicole Zhang, Guochuan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_04540 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures Hommelsheim, Felix Liu, Zhenwei Megow, Nicole Zhang, Guochuan Data Structures and Algorithms F.2.2 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. |
| title | Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures |
| topic | Data Structures and Algorithms F.2.2 |
| url | https://arxiv.org/abs/2501.04540 |