Minimum cost zero skew tree
Let be a rooted tree with real costs and length lower bounds on each edge . We are interested in compute a function , such that , for any root to leaf path , and is minimized.
This is the zero skew tree problem where the tree is fixed.
Here we show how this problem can be solved in time by reducing it to minimum cost flow on 2-terminal series parallel graph. [1]
denote the set of all the children of .
For , and , the graph is the parallel connection of one single edge with cost , lower bound , infinite upper bound and a series-parallel graph . Let the graph for to be the series connection of for all (the connection can be ordered arbitrarily).
The base case is when does not have any children, and is just a single edge with two terminals.
Let , where is the root of . There is a bijection between the edges in and the edges in .
Finding the minimum cost flow of value in with the two terminals gives us the desired solution by going back to the original edge using the bijection.