I have a connected and undirected graph without cycles (i.e. a tree), and I am trying to find a single cut vertex that, when removed, disconnects the graph into a set of connected components. The largest of these components should not have size greater than some threshold. So if one such cut vertex exists, I need to find an algorithm that returns it (possibly in linear time). The only approach I could think of is the following:
- remove from the graph all vertices that have only one outgoing edge (i.e. one neighbour); these are the leaves of the tree
- on the resulting graph, repeat the process until only one vertex remains; this should be the cut vertex
- take back the original graph and remove the cut vertex. Check the size of the largest connected component
This algorithm should run in linear time, but I am not sure it will work in any situation. What's your opinion? The other thing I could think of is that the cut vertex should always be in the minimum vertex cover of the graph, although I don't really know where to go from here...