# Minimum cost zero skew tree

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)≥ℓ(e)$, for any root to leaf path $P$, $∑_{e∈P}f(e)=t$ and $∑_{e∈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(ngn)$ 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∈E(T)$, and $u∈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∈V(T)$ to be the series connection of $P(vu)$ for all $u∈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

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