How to find the minimum number of vertices to join disconnected components of a graph?

Question

Suppose, i have a graph with fixed number of nodes and edges. However, all the nodes doesn't remain active all the time causing the graph disconnected. In this sort of situation, i want to find out the minimal set of vertices, which in case of remaining active, will keep the graph connected all the time.

How can i solve this problem? Can this problem be mapped to any know problem?

Answer 1

This sounds like Connected Dominating Set.

Answer 2

I think that you are looking for the set of articulation points in a graph!

if so, this is an application of Depth-First Search:

http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/