Minimum cost zero skew tree

Problem1

Let $T$ be a rooted tree with real costs $c (e)$ and length lower bounds $ℓ (e)$ on each edge $e$ . We are interested in compute a function $f$ , such that $f (e) \geq ℓ (e)$ , for any root to leaf path $P$ , $\sum_{e \in P} f (e) = t$ and $\sum_{e \in E} c (e) f (e)$ is minimized.

This is the zero skew tree problem where the tree is fixed.

Here we show how this problem can be solved in $O (n lo g n)$ time by reducing it to minimum cost flow on 2-terminal series parallel graph. [1]

$C (v)$ denote the set of all the children of $v$ .

For $vu \in E (T)$ , and $u \in C (v)$ , the graph $P (vu)$ is the parallel connection of one single edge with cost $c (vu)$ , lower bound $ℓ (vu)$ , infinite upper bound and a series-parallel graph $S (u)$ . Let the graph $S (v)$ for $v \in V (T)$ to be the series connection of $P (vu)$ for all $u \in C (v)$ (the connection can be ordered arbitrarily).

The base case is when $u$ does not have any children, and $P (vu)$ is just a single edge with two terminals.

Let $G = S (r)$ , where $r$ is the root of $T$ . There is a bijection between the edges in $T$ and the edges in $G$ .

Finding the minimum cost flow of value $t$ in $G$ with the two terminals gives us the desired solution by going back to the original edge using the bijection.

References

[1]

H. Booth, R.E. Tarjan, Finding the minimum-cost maximum flow in a series-parallel network, Journal of Algorithms. 15 (1993) 416–446 10.1006/jagm.1993.1048.

Posted by Chao Xu on 2015-03-15.

Tags: series-parallel, tree.