My hierarchical clustering paper from SODA defines a class of trees, called "bisectable trees", as part of an NP-completeness proof. A bisectable tree has \( 2^k \) nodes, for some \( k \), and can be partitioned into two smaller bisectable trees by removing a single edge; if an unweighted graph has a spanning tree of this type then it has a particularly nice clustering, but finding such spanning trees is hard.

The NP-completeness proof requires a polynomial time algorithm for testing whether a tree is bisectable, but that's straightforward enough that I didn't bother spelling it out in any detail. This evening, though, while looking at that section of the paper again, I was thinking about the efficiency of bisectable tree recognition algorithms. Here's a simple algorithm:

For each edge \( e \), count the number of descendants of \( e \) (including the endpoint of \( e \) farthest away from the root but not the other endpoint). This can be done for all edges at once by a simple bottom-up traversal of the tree.

Find the edges that have an odd number of descendants. Call each such edge an "odd edge".

If \( T \) does not have exactly \( n/2 \) odd edges, where \( n \) is the number of vertices of \( T \), then \( T \) is not bisectable.

If \( T \) does have \( n/2 \) odd edges, form a tree \( T' \) with \( n/2 \) vertices by contracting each odd edge of \( T \). \( T \) is bisectable if and only if \( T' \) is bisectable; test \( T' \) recursively using the same algorithm.

The basic idea is that, if \( T \) really is bisectable, the odd edges must be the ones at the bottom level of the bisection hierarchy, and the contraction step simplifies the hierarchy by removing the bottom level while leaving the other levels unchanged.

The running time is linear, as the sequence of sizes of trees \( T \), \( T' \), \( T'' \) etc considered by the algorithm forms a geometric sequence.