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

<p>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 <a href="http://en.wikipedia.org/wiki/Vertex_cover" rel="nofollow">Minimum vertex cover</a>.</p>

<p>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 (<a href="http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L22-MinSpanEX1.htm" rel="nofollow">Here you can find an example</a>). </p>

CC BY-SA 3.0
2013-11-10T18:27:12.287Z
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
CC BY-SA 3.0
2013-11-10T09:59:25.803Z
2013-11-10T09:59:25.803Z
giuseppe
<p>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. </p>

<p>Can this problem be mapped to any know problem?</p>

CC BY-SA 3.0
2013-11-10T00:49:35.760Z
What do you mean by "help the graph remain connected all the time"?
David Richerby
CC BY-SA 3.0
2013-11-10T01:20:21.167Z
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ε
CC BY-SA 3.0
2013-11-10T02:50:54.630Z
Sounds like a connected dominating set
Austin Buchanan
<graph-theory><graph-algorithms>
How to find the minimum number of vertices to join disconnected components of a graph?
Mehrab Shahriar
# How to find the minimum number of vertices to join disconnected components of a graph?

(Asked by: username_0 on 2013-11-09)

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?

**Tags:** graph-theory, graph-algorithms

> **Comments:**
> **username_1**: What do you mean by "help the graph remain connected all the time"?  
> **username_2**: 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?  
> **username_3**: Sounds like a connected dominating set  

---

## 1 answers

### Answer by username_4 on 2013-11-10. Score: 1

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](http://en.wikipedia.org/wiki/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](http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L22-MinSpanEX1.htm)).

> **Comments:**
> **username_5**: 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.  

---

