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 is $O(n^2)$. 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 .
Tags: tree, dynamic programming.