The Art Gallery Guardian

Balanced partition for trees


Problem1

Let be a tree with non-negative weights on the edges. Partition the vertices so each side have vertices and minimize the sum of the weights of the edges crossing the partition.

This problem can be solved in time, and it generalizes to graphs with constant treewidth [1].

Here we describe the dynamic programming solution for tree and also show the running time is . This is probably the solution in [1] when the input is a tree, so this might lead to time algorithm for graphs with treewidth .

This problem can be reduced to the following problem by arbitrarily root the tree at a leaf, and replace each vertex with degree into a binary tree with leaves, and assign weight to the internal nodes (except the root) of the replacing binary tree, and infinite edge weight for the edges connecting internal nodes inside the binary tree.

Problem2

Let be a rooted binary tree with non-negative weights on the edges, and weights on the vertices. Partition the vertices so each side have the same weight and minimize the sum of the weights of the edges crossing the partition.

Let to be the sum of the vertex weights of the subtree rooted at . Let to be the subproblem of minimum cost partition of the the vertices of the tree rooted at into vertices such that and . Assume have two children and . There are 4 cases to consider, depending on which of is on the same side of the partition as .

Where taken over all the numbers that make sense. Other cases are similar and simpler. Note that for a particular can be computed time. So computing for all takes time.

Hence the running time would obey . One can show is a solution by induction.

References

[1]
K. Jansen, M. Karpinski, A. Lingas, E. Seidel, Polynomial time approximation schemes for MAX-BISECTION on planar and geometric graphs, SIAM Journal on Computing. 35 (2005) 110–119 10.1137/S009753970139567X.
Posted by Chao Xu on .
Tags: tree, dynamic programming.