Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions

We address long-standing open questions raised by Williamson, Goemans, Vazirani and Mihail pertaining to the design of approximation algorithms for problems in network design via the primal-dual method (Combinatorica 15(3):435-454, 1995). Williamson et al.\ prove an approximation guarantee of two for connectivity augmentation problems where the connectivity requirements can be specified by so-called uncrossable functions. They state: ``Extending our algorithm to handle non-uncrossable functions remains a challenging open problem. The key feature of uncrossable functions is that there exists an optimal dual solution which is laminar. This property characterizes uncrossable functions\dots\ A larger open issue is to explore further the power of the primal-dual approach for obtaining approximation algorithms for other combinatorial optimization problems.'' Our main result proves an $O(1)$-approximation guarantee via the primal-dual method for a class of functions that generalizes the notion of an uncrossable function. We mention that the support of every optimal dual solution could be non-laminar for instances that can be handled by our methods. We present two applications of our main result: (1) An $O(1)$-approximation algorithm for augmenting the family of near-minimum cuts of a graph. (2) An $O(1)$-approximation algorithm for the model of $(p,2)$-Flexible Graph Connectivity. Keywords: { Primal-Dual Method, Network Design, $f$-Connectivity Problem, Near-Minimum Cuts, Approximation Algorithms, Flexible Graph Connectivity. }