Efficiently remove nodes from a connected graph

Question

Suppose you have a connected graph and want to remove k nodes such that the result is still connected. How could you do this efficiently?

It occurs to me that you could find any spanning tree, say by a tree search of any kind. Identify all leaves in the spanning tree, all of these can be removed without disconnecting the remaining vertices. If you have more than k leaves then you're done, but in any tree you're only guaranteed 2 leaves. So you may need to reiterate the process until you've removed k vertices.

That implies O(k) runs of a tree search. Does a more efficient algorithm exist? I don't think you can just look for articulation points or bridge edges because removing a single vertex may suddenly make other vertices which weren't articulation points now turn into articulation points.

Answer 1

Let $G$ be your graph. Compute any spanning tree $T$ of $G$. Perform a postorder visit of $T$, and keep track of the set $D$ of the first $k$ vertices visited ($T$ and $D$ can be computed by the same DFS visit).

The graph $G'$ obtained by deleting the vertices in $D$ from $G$ is still connected (and $T-D$ is a spanning tree of $G'$). To prove this notice that if $v \in D$, then all descendants of $v$ in $T$ must belong to $D$ as well.