A strongly polynomial time algorithm for the maximum supply rate problem on trees

Suppose that we are given a graph whose each vertex is either a supply vertex or a demand vertex and is assigned a nonnegative integer supply or demand value. We consider partitioning into connected components by removing edges from so that each connected component has exactly one supply vertex and there exists a flow in each connected component satisfying the supply/demand constraints. The problem that determines the existence of such a partition is called the partition problem. Ito et al. (2005) showed that the partition problem is -complete in general and it can be solved in linear time if the given graph is a tree. When the graph does not have such a partition, we scale the demand values uniformly by scale factor so that the obtained graph has a desired partition. The maximum supply rate problem is the problem that finds the maximum value of such . Whereas the maximum supply rate problem is -hard in general in the same way as the partition problem, Morishita and Nishizeki (2015) gave a weakly polynomial-time algorithm for the problem on trees.In this paper, we give a first strongly polynomial-time algorithm for the maximum supply rate problem on trees. Our algorithm is based on the dynamic programming technique, in which we compute “surplus” and “deficit” of the supply in subproblems from leaves to the root. We use piecewise linear functions of to represent them, and one of our important contributions is to bound the size of the representation of each function.