# Asymptotic upper bound of Bisecting trees

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.

-

## 1 Answer

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 26, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9386653304100037, "perplexity_flag": "head"}