Tight analysis of the primal-dual method for edge-covering pliable set families

Zeev Nutov · 2025

Read Tight analysis of the primal-dual method for edge-covering pliable set families by Zeev Nutov (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-03910.txt.

Introduction

Zeev Nutov's 2025 paper sharpens the math behind a classic algorithm for covering networks at low cost. The task is to pick the cheapest set of edges that covers every set in a family, and a primal-dual method with a cleanup phase has long been the standard tool.

For pliable set families, which obey weaker crossing rules than the classic case, the method's guarantee had been pushed down in steps from sixteen to ten. A rival claim of eight rested on a faulty proof. Nutov improves the bound to seven for the general case and gives a simple proof of six for graph cuts below a set size, with a slightly better figure for well-connected graphs. Matching examples show the new bounds are tight.

Catalog record

CREATORZeev Nutov
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-03910

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Tight analysis of the primal-dual method for edge-covering pliable set families Zeev Nutov Abstract A classic result of Williamson, Goemans, Mihail, and Vazirani [STOC 1993: 708–717] states that the problem of covering an uncrossable set family by a min-cost edge set admits approximation ratio 2 2 , by a primal-dual algorithm with a reverse delete phase. Bansal, Cheriyan, Grout, and Ibrahimpur [ICALP 2023: 15:1–15:19] showed that this algorithm achieves approximation ratio 16 16 for a larger class of so called γ \gamma -pliable set families, that have much weaker uncrossing properties. The approximation ratio 16 16 was improved to 10 10 in [ 11 ] . Recently, Bansal [ 3 ] stated approximation ratio 8 8 for γ \gamma -pliable families and an improved approximation ratio 5 5 for an important particular case of the family of cuts of size < k <k of a graph H H , but his proof has an error. We will improve the approximation ratio to 7 7 for the former case and give a simple proof of approximation ratio 6 6 for the latter case. Furthermore, if H H is λ \lambda -edge-connected then we will show a slightly better approximation ratio 6 − 1 β + 1 6-\frac{1}{\beta+1} , where β = ⌊ k − 1 ⌈ ( λ + 1 ) / 2 ⌉ ⌋ \beta=\left\lfloor\frac{k-1}{\lceil(\lambda+1)/2\rceil}\right\rfloor . Our analysis is supplemented by examples showing that these approximation ratios are tight for the primal-dual algorithm. The Open University of [email protected] https://orcid.org/0000-0002-6629-3243 ccs Theory of computation Design and analysis of algorithms keywords primal dual method, pliable set family, approximation algorithms † † runningtitle: Tight analysis of the primal-dual method for edge-covering pliable set families † † runningauthor: Zeev Nutov † † copyright: Zeev Nutov 1 Introduction For an edge set or a graph J on node set V and disjoint node subsets S,T\subseteq V let \delta_{J}(S,T) denote the set of edges in J between S and T , and let d_{J}(S,T)=|\delta_{J}(S,T)| be their number; we let \delta_{J}(S)=\delta_{J}(S,V\setminus S) and d_{J}(S)=d_{J}(S,V\setminus S) . An edge set J covers S if d_{J}(S)\geq 1 . The following generic meta-problem captures dozens of specific network design problems, among them Steiner Forest , k -Constrained Forest , Point-to-Point Connection , Steiner Network Augmentation , and many more. Set Family Edge Cover Input: A graph G=(V,E) with edge costs \{c_{e}:e\in E\} , a set family {\cal F} on V . Output: A min-cost edge set J\subseteq E such that d_{J}(S)\geq 1 for all S\in{\cal F} . In this problem the family {\cal F} may not be given explicitly, but we will require that some queries related to {\cal F} can be answered in time polynomial in n=|V| . An inclusion-minimal set in {\cal F} is called an {\cal F} - core , or just a core , if {\cal F} is clear from the context. Following previous work, we will require that for any edge set J , the cores of the residual family {\cal F}^{J}=\{S\in{\cal F}:d_{J}(S)=0\} of {\cal F} (the family of sets in {\cal F} that are uncovered by J ) can be computed in time polynomial in n=|V| . Agrawal, Klein and Ravi [ 2 ] designed and analyzed a primal-dual algorithm for the Steiner Forest problem, and showed that it achieves approximation ratio 2 . A classic result of Goemans and Williamson [ 9 ] from the early 90’s shows by an elegant proof that the same algorithm applies for proper set families, where {\cal F} is proper if it is symmetric ( A\in{\cal F} implies V\setminus A\in{\cal F} ) and has the disjointness property (if A,B are disjoint and A\cup B\in{\cal F} then A\in{\cal F} or B\in{\cal F} ). Slightly later, Williamson, Goemans, Mihail, and Vazirani [ 12 ] (henceforth WGMV) further extended this result to the more general class of uncrossable families ( A\cap B,A\cup B\in{\cal F} or A\setminus B,B\setminus A\in{\cal F} whenever A,B\in{\cal F} ), by adding to the algorithm a novel reverse-delete phase. They posed an open question of extending this algorithm to a larger class of set families and combinatorial optimization problems. However, for 30 years, the class of uncrossable set families remained the most general generic class of set families for which the WGMV algorithm achieves a constant approximation ratio. Bansal, Cheriyan, Grout, and Ibrahimpur [ 4 ] (henceforth BCGI) analyzed the performance of the WGMV algorithm [ 12 ] for the following generic class of set families that arise in variants of capacitated network design problems. Definition 1 . Two sets A,B cross if all the sets A\cap B,V\setminus(A\cup B),A\setminus B,B\setminus A are non-empty. A set family {\cal F} is pliable if \emptyset,V\notin{\cal F} and for any A,B\in{\cal F} at least two of the sets A\cap B,A\cup B,A\setminus B,B\setminus A belong to {\cal F} . We say that {\cal F} is \gamma -pliable if it has the following Property (\gamma) : For any edge set I and sets S_{1}\subset S_{2} in the residual family {\cal F}^{I} , if {\cal F}^{I} -core (an inclusion minimal set in {\cal F}^{I} ) C crosses each of S_{1},S_{2} , then the set D=S_{2}\setminus(S_{1}\cup C) is either empty or belongs to {\cal F}^{I} . BCGI showed that the WGMV algorithm achieves approximation ratio 16 for \gamma -pliable families, and that Property (\gamma) is essential – without it the cost of a solution found by the WGMV algorithm can be \Omega(\sqrt{n}) times the cost of an optimal solution. Another generalization of uncrossable families is considered in [ 10 ] . A set family {\cal F} is semi-uncrossable if for any A,B\in{\cal F} we have that A\cap B\in{\cal F} and one of A\cup B,A\setminus B,B\setminus A is in {\cal F} , or A\setminus B,B\setminus A\in{\cal F} . One can verify that semi-uncrossable families are sandwiched between uncrossable and \gamma -pliable families. The WGMV algorithm achieves the same approximation ratio 2 for semi-uncrossable families, and [ 10 ] shows that many problems can be modeled by semi-uncrossable families that are not uncrossable. The approximation ratio 16 of BCGI [ 4 ] for \gamma -pliable families was improved to 10 in [ 11 ] ; in fact, the analysis in [ 11 ] immediately implies approximation ratio 9 , see Lemma 12 . Recently Bansal [ 3 ] stated an approximation ratio of 8 . Here we improve the approximation ratio to 7 , and show that this bound is asymptotically tight for the WGMV algorithm. Theorem 2 . The Set Family Edge Cover problem with a \gamma -pliable set family {\cal F} admits approximation ratio 7 . A set family {\cal F} is sparse if for any edge set J , every set S\in{\cal F}^{J} crosses at most one {\cal F}^{J} -core. A particular important case of \gamma -pliable families arise from the Small Cuts Cover problem, in which we seek to cover by a min-cost edge set the set family {\cal F}=\{\emptyset\neq S\subset V:d_{H}(S)<k\} of cuts of size/capacity <k of a graph H . Bansal [ 3 ] made an important observation that this family is sparse. To see this, note that if S\in{\cal F} crosses an {\cal F} -core C then C\cap S\notin{\cal F} and C\setminus S\notin{\cal F} by the minimality of C ,

Read the complete text