The Art Gallery Guardian

Minimum cost zero skew tree


Problem1

Let TT be a rooted tree with real costs c(e)c(e) and length lower bounds (e)\ell(e) on each edge ee. We are interested in compute a function ff, such that f(e)(e)f(e)\geq \ell(e), for any root to leaf path PP, ePf(e)=t\sum_{e\in P} f(e)=t and eEc(e)f(e)\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(nlogn)O(n\log n) time by reducing it to minimum cost flow on 2-terminal series parallel graph. [1]

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

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

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

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

Finding the minimum cost flow of value tt in GG 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 .
Tags: series-parallel, tree.