Partitioning graphs of supply and demand

Assume that each vertex of a graph GG is either a supply vertex or a demand vertex and is assigned a positive integer, called a supply or a demand. Each demand vertex can receive “power” from at most one supply vertex through edges in GG. One thus wishes to partition GG into connected components by deleting edges from GG so that each component CC has exactly one supply vertex whose supply is no less than the sum of demands of all demand vertices in CC. If GG does not have such a partition, one wishes to partition GG into connected components so that each component CC either has no supply vertex or has exactly one supply vertex whose supply is no less than the sum of demands in CC, and wishes to maximize the sum of demands in all components with supply vertices. We deal with such a maximization problem, which is NP-hard even for trees and strongly NP-hard for general graphs. In this paper, we show that the problem can be solved in pseudo-polynomial time for series–parallel graphs and partial kk-trees–that is, graphs with bounded tree-width.