{"ID":2897953,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.04473","arxiv_id":"2507.04473","title":"Tight Guarantees for Cut-Relative Survivable Network Design via a Decomposition Technique","abstract":"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.","short_abstract":"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 i...","url_abs":"https://arxiv.org/abs/2507.04473","url_pdf":"https://arxiv.org/pdf/2507.04473v3","authors":"[\"Nikhil Kumar\",\"JJ Nan\",\"Chaitanya Swamy\"]","published":"2025-07-06T17:21:26Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}