Approximating minimum-cost edge-covers of crossing biset-families

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+; (V S ⁺;V S) is the co-biset of Ŝ. Two bisets X̂, Ŷ intersect if ^X 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 ∪ Y = (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 Ŝ 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 NP-hard 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 {pipe}V (X∪Y)≥k+1 that intersect. In this paper we obtain an O(log {pipe}V{pipe})-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: (Formula presented.) Using these generic algorithms, we derive for some network design problems the following approximation ratios: (Formula presented.) for Subset k-Connected Subgraph when all edges with positive cost have their endnodes in the subset.