Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2005-010 (September 19, 2005)

Approximating minimum cost multigraphs of specified edge-connectivity under degree bounds
by Takuro Fukunaga and Hiroshi Nagamochi

pdf File

In this paper, we consider the problem of constructing a minimum cost graph with a specified edge-connectivity under a degree constraint. For a set $V$ of vertices, let $r: {V \choose 2} \rightarrow Z_+$ be a connectivity demand, $a: V \rightarrow Z_+$ be a lower capacity, $b: V \rightarrow Z_+$ be an upper capacity and $c: {V \choose 2} \rightarrow Q_+$ be a metric edge cost. The problem $(V,r,a,b,c)$ asks to find a minimum cost multigraph $G=(V,E)$ with no self-loops such that $\lambda(u,v) \geq r(u,v)$ for each pair $u,v \in V$ and $a(v) \leq d(v) \leq b(v)$ for each $v \in V$, where $\lambda(u,v)$ (resp., $d(v)$) denotes the local-edge-connectivity between $u$ and $v$ (resp., the degree of $v$) in $G$. We show several conditions on functions $r,a,b$ and $c$ for which the above problem admits an approximation algorithm. For example, we give a $\left(2+1/\left\lfloor k/2 \right\rfloor \right)$-approximation algorithm to $(V,r,a,b,c)$ with $r(u,v) \geq 2$, $u,v \in V$ and a uniform $b(v)$, $v \in V$, where $k=\min_{u,v \in V}r(u,v)$. To design the algorithms in this paper, we use our new results on edge-splitting and detachment, which are graph transformations to split vertices while preserving edge-connectivity.