# How to find the minimum number of vertices to join disconnected components of a graph? [closed]

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 that will help the graph remain connected all the time.

Can this problem be mapped to any know problem?

• What do you mean by "help the graph remain connected all the time"? – David Richerby Nov 10 '13 at 0:49
• Voting to close as unclear. What exactly is the input to your problem, besides the graph? The inactive vertices? Just the number of inactive vertices? The probability that each vertex is inactive? Something else? Does the set of inactive vertices change over time? What precise property do you want the "minimal set of vertices" to have? What precisely does "help the graph remain connected" mean? Do you want to guarantee that the graph (which graph?) is always connected, or maximize the probability that it is connected, or minimize the number of components, or something else? – Jeffε Nov 10 '13 at 1:20
• Sounds like a connected dominating set – Austin Buchanan Nov 10 '13 at 2:50

• 3) If you want to find a set $S$ of inactive vertices such that the graph induced by the active and $S$ is connected it is a Steiner tree problem. – Martin Vatshelle Nov 10 '13 at 18:27