Approximating Directed Weighted-Degree Constrained Networks

Given a graph H = (V, F) with edge weights {omega(e) : e is an element of F}, the weighted degree of a node nu in H is Sigma{omega(nu u) : nu u is an element of F}. We give bicriteria approximation algorithms for problems that seek to find a minimum cost directed graph that satisfies both intersecting supermodular connectivity requirements and weighted degree constraints. The input to such problems is a directed graph G = (V, E), edge-costs {c(e) : e is an element of E}, edge-weights {omega(e) : e is an element of E}, an intersecting supermodular set-function f on V, and degree bounds {b(nu) : nu is an element of V}. The goal is to find a minimum cost f-connected subgraph H = (V, F) (namely, at least f(S) edges in F enter every S subset of V) of G with weighted degrees <= b(nu). Our algorithm computes a solution of cost <= 2. opt, so that the weighted degree of every nu is an element of V is at most: 7b(nu) for arbitrary f and 5b(nu) for a 0, 1-valued f; 2b(nu) + 4 for arbitrary f and 2b(nu) + 2 for a 0, 1-valued f in the case of unit weights. Another algorithm computes a solution of cost <= 3. opt and weighted degrees <= 6b(nu). We obtain similar results when there are both indegree and outdegree constraints, and better results when there are indegree constraints only: a (1, 4)-approximation algorithm for arbitrary weights and a polynomial time algorithm for unit weights. Finally, we consider the problem of packing maximum number k of edge-disjoint arborescences so that their union satisfies weighted degree constraints, and give an algorithm that computes a solution of value at least [k/36].