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:
@techreport{egres-10-13,
AUTHOR | = | {Hirai, Hiroshi and Pap, Gyula}, |
TITLE | = | {Tree metrics and edge-disjoint S-paths}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2010}, |
NUMBER | = | {TR-2010-13} |