Find cut vertex in tree with constraint on the size of largest component

Question

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...

Answer 1

Given a graph $G$ and a threshold $k$, you are looking for an articulation point whose removal divides the graph into connected components all of size $\le k$. This can be done in linear time.

First, construct the block-cut tree of $G$. This is a tree $T$ that has one node for each biconnected component of $G$ and one node for each articulation point of $G$, with an edge between a biconnected component $c$ and an articulation point $a$ if $a$ is contained in $c$. The block-cut tree can be constructed in linear time.

Now you want to find an articulation node in the tree $T$ whose removal disconnects the tree into connected components all of size $\le k$. This can be done in linear time. In particular, the algorithm problem is the following:

Given a tree $T$ and a threshold tree, we are looking for a node in $T$ whose removal disconnects $T$ into connected components all of size $\le k$.

This can be done in linear time. You pick an arbitrary node to be the root of $T$. With a bottom-up traversal, you annotate each node with the number of descendants it has. Now if we focus on a single node, we can use the annotation on its neighbors to determine the size of all connected components that result if we delete that node, in time proportional to the number of neighbors it has. This lets you check whether deleting that node would leave you with connected components all of size $\le k$. So iterate over all nodes and check whether any qualifies. The total amount of work is proportional to the number of edges in the tree, which is proportional to the number of vertices in the tree.

Thus, the total running time is linear in the size of $G$.

Answer 2

Your algorithm may not work. What you describe, in fact, is an algorithm for computing the center of the tree. The following is a brief theory behind this algorithm.

The distance, denoted by $dist(v,u)$, between two vertices $u$ and $v$ is defined as the shortest path between $u$ and $v$. The eccentricity of a vertex $v$ is defined as $$ \epsilon(v)=\max_{u \in V}\{dist(v,u)\}$$ In simple words $\epsilon(v)$ is the maximum among all distances from the $v$ to a vertex $u$.

We define the center of a graph $G$ is the set of vertices with minimum eccentricity. Observe that step-by-step leaf removal in your algorithm does not change the eccentricity of the center.

Your algorithm essentially computes the center of the tree but the following is a counterexample. This tree

has the center $v_c$. Your algorithm will return $v_c$ as the cut vertex. But if your threshold is $3$ then the optimal cut vertex would be the vertex $u$.