Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The question is :

B-3 Bisecting trees

Many divide-and-conquer algorithms that operate on graphs require that the graph be bisected into two nearly equal-sized subgraphs, which are induced by a partition of the vertices. This problem investigates bisections of trees formed by removing a small number of edges. We require that whenever two vertices end up in the same subtree after removing edges, then they must be in the same partition.

c. Show that by removing at most $O(lg(n))$ edges, we can partition the vertices of any n-vertex binary tree into two sets A and B such that $|A| = \lfloor\frac{n}2\rfloor$ and $|B| = \lceil\frac{n}2\rceil$

I've resolved a related question here, but I'm not sure if it's helpful for this problem.

share|improve this question
add comment

1 Answer 1

Strengthen the statement to:

For any $k=1$, $\dots$, $n-1$, by removing at most $3 \lg n$ edges, we can partition the vertices of any $n$-vertex binary tree into two sets, one of which contains $k$ vertices and the other of which contains $n-k$ vertices.

The statement can then be proven by induction on $n$. If $n=1$, the statement is vacuously true. Otherwise, use the previous result to remove an edge to partition the tree into subtrees whose sets of vertices, $A$ and $B$, say, are such that $|A|\le 3n/4$, $|B|\le 3n/4$. If $|A|=k$, we are done. If $|A|>k$, use the induction hypothesis to partition $A$ into a piece of size $k$ and a piece of size $|A|-k$; otherwise, $|A|<k$, so partition $B$ into a piece of size $k-|A|$ and a piece of size $n-k$. By the induction hypothesis, this removes at most $1+3 \lg(\frac{3}{4}n)\le 3\lg n$ edges in all.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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