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?

  • $\begingroup$ What do you mean by "help the graph remain connected all the time"? $\endgroup$ – David Richerby Nov 10 '13 at 0:49
  • 3
    $\begingroup$ 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? $\endgroup$ – Jeffε Nov 10 '13 at 1:20
  • $\begingroup$ Sounds like a connected dominating set $\endgroup$ – Austin Buchanan Nov 10 '13 at 2:50

I don't know if I understood your question. But there are two possibilities:

1)If you want to know the minimum set that cover all the edges this (in the general case) is a NP-complete problem and is called Minimum vertex cover.

2)If you want to know the set of vertices with which every other vertex are connected at least at a vertex in the set this can be solved in P time solving the minimum spanning tree problem for unweighted graph (Here you can find an example).

  • 1
    $\begingroup$ 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. $\endgroup$ – Martin Vatshelle Nov 10 '13 at 18:27

Not the answer you're looking for? Browse other questions tagged or ask your own question.