# Balanced partition for trees

Problem1

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

This problem can be solved in $$O(n^3)$$ 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 of $$O(n^2)$$ is possible. This is probably the solution in [1] when the input is a tree, so this might lead to $$O(2^kn^2)$$ time algorithm for graphs with treewidth $$k$$.

This problem can be reduced to the following problem by arbitrarily root the tree at a leaf, and replace each vertex with degree $$d+1$$ into a binary tree with $$d$$ leaves, and assign weight $$0$$ 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 $$T$$ be a rooted binary tree with non-negative weights on the edges, and $$0-1$$ 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 $$W(v)$$ to be the sum of the vertex weights of the subtree rooted at $$v$$. Let $$D(v,k)$$ to be the subproblem of minimum cost partition of the the vertices of the tree rooted at $$v$$ into vertices $$(A,B)$$ such that $$v\in A$$ and $$\sum_{a\in A} {w(a)}=k$$. Assume $$v$$ have two children $$u$$ and $$w$$. There are 4 cases to consider, depending on which of $$\{u,w\}$$ is on the same side of the partition as $$v$$.

$D(v,k) = \min \begin{cases} \min_{i} D(u,i) + D(w,k-w(v)-i)\\ \min_{i} w(vu) + D(u,W(u)-i) + D(w,k-w(v)-i)\\ \min_{i} w(vw) + D(u,i) + D(w,W(w) - (k-w(v)-i))\\ \min_{i} w(vu) + w(vw) + D(u,W(u)-i) + D(w,W(w)-(k-w(v)-i))\\ \end{cases}$

Where $$i$$ taken over all the numbers that make sense. Other cases are similar and simpler. Note that $$D(v,k)$$ for a particular $$k$$ can be computed $$O(k \min\{W(u),W(w)\})$$ time. So computing $$D(v,k)$$ for all $$1\leq k\leq W(v)$$ takes $$O(W(u)W(w))$$ time.

Hence the running time would obey $$T(n) \leq \max_{a+b=n} T(a)+T(b)+O(ab)$$. One can show $$T(n)=O(n^2)$$ 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 2016-04-21.
Tags: tree, dynamic programming.