The Art Gallery Guardian

Balanced partition for trees


Problem1

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

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

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

D(v,k)=min{miniD(u,i)+D(w,kw(v)i)miniw(vu)+D(u,W(u)i)+D(w,kw(v)i)miniw(vw)+D(u,i)+D(w,W(w)(kw(v)i))miniw(vu)+w(vw)+D(u,W(u)i)+D(w,W(w)(kw(v)i))\displaystyle 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 ii taken over all the numbers that make sense. Other cases are similar and simpler. Note that D(v,k)D(v,k) for a particular kk can be computed O(kmin{W(u),W(w)})O(k \min\{W(u),W(w)\}) time. So computing D(v,k)D(v,k) for all 1kW(v)1\leq k\leq W(v) takes O(W(u)W(w))O(W(u)W(w)) time.

Hence the running time would obey T(n)maxa+b=nT(a)+T(b)+O(ab)T(n) \leq \max_{a+b=n} T(a)+T(b)+O(ab). One can show T(n)=O(n2)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.