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 G into connected components by removing edges from G 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 \(\mathcal {NP}\)-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 r so that the obtained graph has a desired partition. The maximum supply rate problem is the problem that finds the maximum value of such r. Whereas the maximum supply rate problem is \(\mathcal {NP}\)-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.