**Reference**:- Takehiro Ito, Erik D. Demaine, Xiao Zhou, and Takao Nishizeki, “Approximability for Partitioning Graphs with Supply and Demand”, in
*Proceedings of the 17th Annual International Symposium on Algorithms and Computation (ISAAC 2006)*, Lecture Notes in Computer Science, volume 4288, Calcutta, India, December 18–20, 2006, pages 121–130. **Abstract**:-
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 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 = NP. We then present a fully polynomial-time approximation scheme (FPTAS) for series-parallel graphs having exactly one supply vertex. The FPTAS can be easily extended for partial*k*-trees, that is, graphs with bounded treewidth. **Comments**:- This paper is also available from SpringerLink.
**Copyright**:- The paper is \copyright Springer-Verlag.
**Availability**:- The paper is available in PostScript (1262k), gzipped PostScript (567k), and PDF (158k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- SupplyDemand_JDA (Approximability of Partitioning Graphs with Supply and Demand)

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.