Network design via iterative rounding of setpair relaxations (Q858116)

An important class of network design problems asks for finding a minimum cost sub-network \(H\) of a given network \(G\) that satisfies some connectivity requirements. Perhaps the most famous work in this area is the seminal paper of \textit{M. X. Goemans} and \textit{D. P. Williamson} [SIAM J. Comput. 24, 296--317 (1995; Zbl 0834.68055)] which proposes a method for finding sub-networks satisfying a fairly general class of edge-connectivity requirements. The present paper continues a long succession of papers spawned by Goemans and Williamson's work, and it focuses on finding sub-networks satisfying given vertex-connectivity requirements. The vertex-connectivity requirements are expressed as an integer program whose constraints consist of a set of edge requirements over a family of setpairs. A setpair is simply a pair \((X,Y)\) of non-empty disjoint vertex sets. The edge connectivity requirements for a given setpair \((X,Y)\) is given by a requirement function \(f(X,Y)\) stating that the chosen subgraph must have at least \(f(X,Y)\) edges with one endpoint in \(X\) and the other endpoint in \(Y\). One of the problems considered in the paper is the \(k\)-vertex connectivity problem. Given a graph \(G=(V,E)\) with non-negative edge costs, the goal is to find a minimum cost, connected spanning subgraph \(H\), that remains connected even if \(k-1\) vertices are removed from it. This problem can be formulated as an integer program with the requirement function \(f(X,Y) =\max \{0,k-| V\setminus(X \cup Y)| \}\) defined over all setpairs \((X,Y)\) where \(X,Y \neq\emptyset\). The paper presents an approximation algorithm for solving the above kind of integer programs for the particular case when the requirement function \(f(X,Y)\) is skew bisupermodular. (Skew bisupermodular functions are a generalization of weakly supermodular and crossing bisupermodular functions.) This algorithm yields an \(O(\sqrt{n/(1-k/n)})\)-approximation algorithm for the \(k\)-vertex connectivity problem. This results holds, both, when the input graph is directed and when it is undirected. The authors also derive a 2-approximation algorithm for a generalization of the Steiner tree problem called the element connectivity problem. Here we are given a graph \(G=(V,E)\) with non-negative edge costs. There is a set of terminal vertices \(T \subseteq V\) and connectivity requirements \(r_{ij}\) for each pair of distinct terminals \(i\) and \(j\). Edges and non-terminal vertices are called elements. The problem is to find a minimum cost subgraph \(H\) of \(G\) that contains \(r_{ij}\) element disjoint paths between each pair of terminals \((i,j)\).