Algorithm For Vertex Removal From Tree

Question

When a vertex and its incident edges are removed from a tree, a collection of subtrees remains. Write an algorithm that, given a graph that is a tree with n vertices, finds a vertex v whose removal leaves no subtree with more than n/2 vertices.

I have attempted this problem using a modified DFS approach as well as a bridge finding algorithm. Any help would be much appreciated.

Answer 1

Create a recursive function that does a post-order traversal of the tree.

The function returns the subtree size and a vertex, or the vertex can be global (in which case you just set it instead of returning it).

Call the function for the root.

1. Call the function on each child's subtree.

2. If one of those calls returned a vertex, return that vertex.

3. Return the current vertex if these conditions hold:

   • Each child's subtree has less than or equal to n/2 vertices.

   • The sum of children's subtree sizes is greater than or equal to (n-1)/2, i.e. the subtree 'above' the current has less than or equal to n/2 nodes.

4. Return the sum of children's subtree sizes + 1 as the subtree size.

Running time: O(n).

I'm assuming you've already got the size of the tree - n - if not, you'll need to start off with another traversal to get this size (which doesn't affect the O(n) running time).