Tree metrics and edge-disjoint S-paths

Hiroshi Hirai, Gyula Pap

Published in:


Given an undirected graph $G=(V,E)$ with a terminal set $S \subseteq V$, a weight function $\mu:{S \choose 2} \to \ZZ_+$ on on terminal pairs, and an edge-cost $a: E \to \ZZ_+$, the $\mu$-weighted minimum-cost edge-disjoint $S$-paths problem ($\mu$-CEDP) is to maximize $\sum_{P \in {\cal P}} \mu(s_P,t_P) - a(P)$ over all edge-disjoint sets ${\cal P}$ of $S$-paths, where $s_P,t_P$ denote the ends of $P$ and $a(P)$ is the sum of edge-cost $a(e)$ over edges $e$ in $P$.
Our main result is a complete characterization of terminal weights $\mu$ for which $\mu$-CEDP is tractable and admits a combinatorial min-max theorem. We prove that if $\mu$ is a tree metric, then $\mu$-CEDP is solvable in polynomial time and has a combinatorial min-max formula, which extends Mader's edge-disjoint $S$-paths theorem and its minimum-cost generalization by Karzanov. Our min-max theorem includes the dual half-integrality, which was earlier conjectured by Karzanov for a special case. We also prove that $\mu$-EDP, which is $\mu$-CEDP with $a = 0$, is NP-hard if $\mu$ is not a truncated tree metric, where a truncated tree metric is a weight function represented as pairwise distances between balls in a tree. On the other hand, $\mu$-CEDP for a truncated tree metric $\mu$ reduces to $\mu'$-CEDP for a tree metric $\mu'$. Thus our result is best possible unless P $=$ NP. As an application, we get a good approximation algorithm for $\mu$-EDP with ``near" tree metric $\mu$ by utilizing results from the theory of low-distortion embedding.

Previous version can be found here.

Bibtex entry:

AUTHOR = {Hirai, Hiroshi and Pap, Gyula},
TITLE = {Tree metrics and edge-disjoint S-paths},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2010},
NUMBER = {TR-2010-13}

Last modification: 13.3.2018. Please email your comments to Tamás Király!