# Minimum cost zero skew tree

Problem1

Let $$T$$ be a rooted tree with real costs $$c(e)$$ and length lower bounds $$\ell(e)$$ on each edge $$e$$. We are interested in compute a function $$f$$, such that $$f(e)\geq \ell(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\log 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 $$\ell(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. 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.