On weighted multiway cuts in trees

A min-max theorem is developed for the multiway cut problem of edge-weighted trees. The authors present a polynomial time algorithm to construct an optimal dual solution, if edge weights come in unary representation. Applications to biology also require some more complex edge weights. The authors describe a dynamic programming type algorithm for this more general problem from biology and show that our min-max theorem does not apply to it.