Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2008-005 (April 24, 2008)

Network Design with Weighted Degree Constraints
by Takuro Fukunaga, Hiroshi Nagamochi

pdf File

In an undirected graph $G=(V,E)$ with a weight function $w: E \times V \rightarrow \Qset_+$, the weighted degree $d_w(v;E)$ of a vertex $v$ is defined as $\sum\{w(e,v)\mid e\in E {\rm ~incident~with~} v\}$. In this paper, we consider a network design problem with upper-bound on weighted degree of each vertex. Inputs of the problem are an undirected graph $G=(V,E)$ with $E = E_1 \: \dot{\cup} \: E_2 \: \dot{\cup}\: E_3$, weights $w_1: E_1 \times V \rightarrow \Qset_+$, $\mu: E_2 \rightarrow \Qset_+$, $\nu: E_3 \rightarrow \Qset_+$, an edge-cost $c: E \rightarrow \Qset$, a skew supermodular set function $f: 2^V \rightarrow \Nset$, and a degree-bound $b:A \rightarrow \Qset_+$. A solution consists of $F \subseteq E$, and weights $w_i: F_i \times V \rightarrow \Qset_+$ for $i \in \{2,3\}$, where $F_i$ stands for $F \cap E_i$. It is defined to be feasible if the cut-size of $U$ in $(V,F)$ is at least $f(U)$ for $U \subset V$, $w_2(e,u) + w_2(e,v)=\mu(e)$ for $e =uv \in F_2$, $\{w_3(e,u),w_3(e,v)\}=\{0,\nu(e)\}$ for $e =uv \in F_3$, and $d_{w_1}(v; F_1) + d_{w_2}(v; F_2) + d_{w_3}(v; F_3)\leq b(v)$ for each $v \in V$. The goal of this problem is to find a feasible solution that minimizes its cost $\sum_{e \in F}c(e)$. Relaxing the constraints on weighted degree, we propose a bi-criteria approximation algorithm based on the iterative rounding, which has been successfully applied to the degree-bounded spanning tree problem. Our algorithm computes a $(2,9+5\theta)$-approximate solution, where $\theta=\max\{b(u)/b(v),b(v)/b(u) \mid uv \in E_2\}$ if $E_2 \neq \emptyset$ and $\theta=0$ if $E_2=\emptyset$, where $(\alpha,\beta)$-approximate solution has the cost at most $\alpha$ times the optimal and the weighted degree of $v$ at most $\beta b(v)$. We also give a $(1,5+3\theta)$-approximation algorithm to the case of $f(U)=1$ for $U \subset V$. Moreover, a problem minimizing the maximum weighted degree of vertices is also discussed.