APPROXIMATING MINIMUM-COST EDGE-COVERS OF CROSSING MINIMUM-COST EDGE-COVERS

摘要

Part of this paper appeared in the preliminary version [16]. An ordered pair ? = (S,S~+) of subsets of a groundset V is called a biset if S ? S~+; (VS~+,VS) is the co-biset of S. Two bisets X,? intersect if X ∩ Y ≠ ? and cross if both X ∩ Y ≠? and X~+ ∪Y~+ ≠ V. The intersection and the union of two bisets X,? are defined by X∩? = (X∩Y,X~+∩Y~+) and X∪? = (X∪Y,X~+∪Y~+). A biset-family F is crossing (intersecting) if X∩?,X∪? ∈F for any X,? ∈ F that cross (intersect). A directed edge covers a biset S if it goes from S to V S~+. We consider the problem of covering a crossing biset-family F by a minimum-cost set of directed edges. While for intersecting F, a standard primal-dual algorithm computes an optimal solution, the approximability of the case of crossing F is not yet understood, as it includes several NPhard problems, for which a poly-logarithmic approximation was discovered only recently or is not known. Let us say that a biset-family F is k-regular if X ∩ ?, X ∪ ? ∈ F for any X,? ∈F with |V(X∪Y)|≥k+l that intersect. In this paper we obtain an O(log|V|)-approximation algorithm for arbitrary crossing F; if in addition both F and the family of co-bisets of F are k-regular, our ratios are: O (log (|V|/|(|V|-k)) if |S~+S| = k for all ? ∈ F, and O ((|V|)/(|V|-k)log (|V|)/(|V|-k)) if |S~+S|≤k for all ? ∈ F. Using these generic algorithms, we derive for some network design problems the following approximation ratios: O (log k ?log n/(n-k)) for k-Connected Subgraph, and O(log k) ? min{n/(n-k) log n/(n-k), log k} for Subset k-Connected Subgraph when all edges with positive cost have their endnodes in the subset.