2
$\begingroup$

My algorithm book states that any n-vertex binary tree T can be partitioned by just removing a single edge into two disconnected trees A and B where neither of them has more than 3/4 of the vertices.

It sounds like it should be simple to create such a tree, but I can't imagine one, my bisections are always better balanced. Can somebody show me a tree where the vertex distribution of 3/4 to 1/4?

This is from "Introduction to Algorithms" by Thomas Cormen, 3rd edition, MIT Press. Appendix B, Problems B-3.

$\endgroup$
1
$\begingroup$

Consider a simple binary tree $T$ with only 4 nodes: The root of $T$ is $A$. $A$ has a left child $B$ which has two children $C$ and $D$.

$\endgroup$
  • $\begingroup$ Ouch. Yes, so simple that I didn't get it. Thanks a lot. $\endgroup$ – mkraemerx May 16 '15 at 9:16
1
$\begingroup$

Nobody said that $3/4$ was the optimal number. In fact, it seems like $2/3$ might be achievable. Starting at the root, consider a walk which always chooses the child with the larger subtree. Consider the first time that you reach a node whose subtree contains less than $2/3$ of the nodes. Its parent's subtree contains more than $2/3$ of the nodes, so the subtree rooted at its larger child contains at least $1/3$ of the nodes. So we have found a node whose subtree contains between $1/3$ and $2/3$ of the nodes.

Considering the tree with one root and two children, we see that we can't in general obtain a better balanced partition.

$\endgroup$
  • $\begingroup$ Yes, that is indeed what it seems to me, too. But the book (which has a quite good reputation) states, that the worst case for any tree graph is 3/4. I'd like to understand that. I tried to find a graph which does not allow a better balanced bisection than 3/4 to 1/4 with removal of 1 edge, but I failed. In the worst case I end up with 2/3, too. So, is the book wrong? $\endgroup$ – mkraemerx May 15 '15 at 23:41
  • 1
    $\begingroup$ Perhaps. Nobody's perfect. It could also be that my proof sketch doesn't work. Fortunately, there is a remedy. You can check to see whether my proof works. If it does, then 3/4 can be lowered to 2/3. Otherwise, you will probably get a counterexample to 2/3, in which the best constant will probably be 3/4. $\endgroup$ – Yuval Filmus May 15 '15 at 23:44
  • $\begingroup$ I think the little flaw of your argument lies in the "rounding" of rational numbers to integers. (Consider a simple binary tree $T$ with only 4 nodes: The root of $T$ is $A$. $A$ has a left child $B$ which has two children $C$ and $D$.) $\endgroup$ – hengxin May 16 '15 at 7:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.