Approximating minimum power covers of intersecting families and directed edge-connectivity problems

Given a (directed) graph with costs on the edges, the power of a node is the maximum cost of an edge leaving it, and the power of the graph is the sum of the powers of its nodes. Let G = (V, E) be a graph with edge costs {c (e) : e ∈ E} and let k be an integer. We consider problems that seek to find a min-power spanning subgraph G of G that satisfies a prescribed edge-connectivity property. In the Min-Powerk-Edge-Outconnected Subgraph problem we are given a root r ∈ V, and require that G contains k pairwise edge-disjoint r v-paths for all v ∈ V - r. In the Min-Powerk-Edge-Connected Subgraph problem G is required to be k-edge-connected. For k = 1, these problems are at least as hard as the Set-Cover problem and thus have an Ω (ln | V |) approximation threshold. For k = Ω (n^ε), they are unlikely to admit a polylogarithmic approximation ratio [15]. We give approximation algorithms with ratio O (k ln | V |). Our algorithms are based on a more general O (ln | V |)-approximation algorithm for the problem of finding a min-power directed edge-cover of an intersecting set-family; a set-family F is intersecting if X ∩ Y, X ∪ Y ∈ F for any intersecting X, Y ∈ F, and an edge set I covers F if for every X ∈ F there is an edge in I entering X.