# 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?

## closed as unclear what you're asking by Jeffε, András Salamon, David Eppstein, KavehNov 17 '13 at 5:44

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• 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