Polynomial algorithms for partitioning a tree into single-center subtrees to minimize flat service costs.

This paper deals with the following graph partitioningproblem. Consider a connected graph withnnodes,pof which are centers, while the remaining ones are units.For each unit-center pair there is a fixed service cost andthe goal is to find a partition into connected componentssuch that each component contains only one center andthe total service cost is minimum. This problem is knownto be NP-hard on general graphs, and here we show thatit remains such even if the service cost is monotone andthe graph is bipartite. However, in this paper we derivesome polynomial time algorithms for trees. For this classof graphs we provide several reformulations of the prob-lem as integer linear programs proving the integralityof the corresponding polyhedra. As a consequence, thetree partitioning problem can be solved in polynomialtime either by linear programming or by suitable convexnondifferentiable optimization algorithms. Moreover, wedevelop a dynamic programming algorithm, whose recur-sion is based on sequences of minimum weight closureproblems, which solves the problem on trees inO(np)time.