2026-07-21T12:35:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24506 2025-12-16T14:00:07Z ddc:004 open_access

Tight Guarantees for Cut-Relative Survivable Network Design via a Decomposition Technique Kumar, Nikhil Nan, J. J. Swamy, Chaitanya Approximation algorithms Network Design Cut-requirement functions Weak Supermodularity Iterative rounding LP rounding algorithms In the classical survivable-network-design problem (SNDP), we are given an undirected graph G = (V, E), non-negative edge costs, and some k tuples (s_i,t_i,r_i), where s_i,t_i ∈ V and r_i ∈ ℤ_+. The objective is to find a minimum-cost subset H ⊆ E such that each s_i-t_i pair remains connected even after the failure of any r_i-1 edges. It is well-known that SNDP can be equivalently modeled using a weakly-supermodular cut-requirement function f, where the objective is to find the minimum-cost subset of edges that picks at least f(S) edges across every cut S ⊆ V. Recently, motivated by fault-tolerance in graph spanners, Dinitz, Koranteng, and Kortsartz proposed a variant of SNDP that enforces a relative level of fault tolerance with respect to G. Even if a feasible SNDP-solution may not exist due to G lacking the required fault-tolerance, the goal is to find a solution H that is at least as fault-tolerant as G itself. They formalize the latter condition in terms of paths and fault-sets, which gives rise to path-relative SNDP (which they call relative SNDP). Along these lines, we introduce a new model of relative network design, called 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 ⊆ 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 novel decomposition technique to circumvent this difficulty and use it to give a tight 2-approximation algorithm for CR-SNDP. We also show some new hardness results for these relative-SNDP problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nikhil Kumar and J. J. Nan and Chaitanya Swamy 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.38 urn:nbn:de:0030-drops-245061 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.38 eng https://creativecommons.org/licenses/by/4.0/legalcode