Tight Guarantees for Cut-Relative Survivable Network Design via a Decomposition Technique
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_ | 1866908499859996672 |
|---|---|
| author | Kumar, Nikhil Nan, JJ Swamy, Chaitanya |
| author_facet | Kumar, Nikhil Nan, JJ Swamy, Chaitanya |
| contents | In the classical \emph{survivable-network-design problem} (SNDP), we are given an undirected graph $G = (V, E)$, non-negative edge costs, and some $(s_i,t_i,r_i)$ tuples, where $s_i,t_i\in V$ and $r_i\in\mathbb{Z}_+$. We seek a minimum-cost subset $H \subseteq E$ such that each $s_i$-$t_i$ pair remains connected even if any $r_i-1$ edges fail. It is well-known that SNDP can be equivalently modeled using a weakly-supermodular \emph{cut-requirement function} $f$, where we seek a minimum-cost edge-set containing at least $f(S)$ edges across every cut $S \subseteq V$.
Recently, Dinitz et al. proposed a variant of SNDP that enforces a \emph{relative} level of fault tolerance with respect to $G$, where the goal is to find a solution $H$ that is at least as fault-tolerant as $G$ itself. They formalize this in terms of paths and fault-sets, which gives rise to \emph{path-relative SNDP}. Along these lines, we introduce a new model of relative network design, called \emph{cut-relative SNDP} (CR-SNDP), where the goal is to select a minimum-cost subset of edges that satisfies the given (weakly-supermodular) cut-requirement function to the maximum extent possible, i.e., by picking $\min\{f(S),|δ_G(S)|\}$ edges across every cut $S\subseteq V$.
Unlike SNDP, the cut-relative and path-relative versions of SNDP are not equivalent. The resulting cut-requirement function for CR-SNDP (as also path-relative SNDP) is not weakly supermodular, and extreme-point solutions to the natural LP-relaxation need not correspond to a laminar family of tight cut constraints. Consequently, standard techniques cannot be used directly to design approximation algorithms for this problem. We develop a \emph{novel decomposition technique} to circumvent this difficulty and use it to give a \emph{tight $2$-approximation algorithm for CR-SNDP}. We also show new hardness results for these relative-SNDP problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_04473 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tight Guarantees for Cut-Relative Survivable Network Design via a Decomposition Technique Kumar, Nikhil Nan, JJ Swamy, Chaitanya Data Structures and Algorithms F.2.2; G.2 In the classical \emph{survivable-network-design problem} (SNDP), we are given an undirected graph $G = (V, E)$, non-negative edge costs, and some $(s_i,t_i,r_i)$ tuples, where $s_i,t_i\in V$ and $r_i\in\mathbb{Z}_+$. We seek a minimum-cost subset $H \subseteq E$ such that each $s_i$-$t_i$ pair remains connected even if any $r_i-1$ edges fail. It is well-known that SNDP can be equivalently modeled using a weakly-supermodular \emph{cut-requirement function} $f$, where we seek a minimum-cost edge-set containing at least $f(S)$ edges across every cut $S \subseteq V$. Recently, Dinitz et al. proposed a variant of SNDP that enforces a \emph{relative} level of fault tolerance with respect to $G$, where the goal is to find a solution $H$ that is at least as fault-tolerant as $G$ itself. They formalize this in terms of paths and fault-sets, which gives rise to \emph{path-relative SNDP}. Along these lines, we introduce a new model of relative network design, called \emph{cut-relative SNDP} (CR-SNDP), where the goal is to select a minimum-cost subset of edges that satisfies the given (weakly-supermodular) cut-requirement function to the maximum extent possible, i.e., by picking $\min\{f(S),|δ_G(S)|\}$ edges across every cut $S\subseteq V$. Unlike SNDP, the cut-relative and path-relative versions of SNDP are not equivalent. The resulting cut-requirement function for CR-SNDP (as also path-relative SNDP) is not weakly supermodular, and extreme-point solutions to the natural LP-relaxation need not correspond to a laminar family of tight cut constraints. Consequently, standard techniques cannot be used directly to design approximation algorithms for this problem. We develop a \emph{novel decomposition technique} to circumvent this difficulty and use it to give a \emph{tight $2$-approximation algorithm for CR-SNDP}. We also show new hardness results for these relative-SNDP problems. |
| title | Tight Guarantees for Cut-Relative Survivable Network Design via a Decomposition Technique |
| topic | Data Structures and Algorithms F.2.2; G.2 |
| url | https://arxiv.org/abs/2507.04473 |