In search of a graph algorithm...

[kjkrum]

I have only a basic knowledge of graph theory and even less of set theory, so I hope I can accurately describe what I want to do.

In graph theory, a cut-vertex is a vertex which, when removed from a graph, increases the number of connected components in the graph. I'm looking for a way to find minimal sets of up to n vertices which have the property that when all members of the set are removed from the graph, the number of connected components in the graph is increased.

I have an idea, but it might be naive. I'm thinking I could perform a breadth-first search from each vertex of the graph, and then find the shortest paths from the original vertex to every other vertex. These paths would be sets of integers, with each integer identifying a vertex. Call the set containing these sets of integers A. The problem would then be to identify a set B containing n or fewer integers such that the intersection of B with every set in A is non-empty.