Approximability of partitioning graphs with supply and demand

Suppose that each vertex of a graph G is either a supply vertex or a demand vertex and is assigned a positive real number, called the supply or the demand. Each demand vertex can receive “power” from at most one supply vertex through edges in G. One thus wishes to partition G into connected components by deleting edges from G so that each component C either has no supply vertex or has exactly one supply vertex whose supply is at least the sum of demands in C  , and wishes to maximize the fulfillment, that is, the sum of demands in all components with supply vertices. This maximization problem is known to be NP-hard even for trees having exactly one supply vertex and strongly NP-hard for general graphs. In this paper, we focus on the approximability of the problem. We first show that the problem is MAXSNP-hard and hence there is no polynomial-time approximation scheme (PTAS) for general graphs unless P=NPP=NP. We then present a fully polynomial-time approximation scheme (FPTAS) for series-parallel graphs having exactly one supply vertex.