Disconnect all vertices in a graph - Algorithm

Question

I am looking for an algorithm that finds minimal subset of vertices such that by removing this subset (and edges connecting these vertices) from graph all other vertices become unconnected (i.e. the graph won't have any edges).

Is there such algorithm?
If not: Could you recommend some kind of heuristics to designate the vertices.

I have a basic knowledge of graph theory so please excuse any incorrectness.

Questions asking us to recommend or find a book, tool, software library, tutorial or other off-site resource are off-topic for Stack Overflow as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it. — AStopher, Jun 23 '15 at 12:21
@cybermonkey There is no such a request for recommendation. This question is on-topic, and there is a clear answer to it (See @AmiTavory's). (Obviously there are more answers, but none will be spam of opinionated answers). He is describing a problem, and he is getting an answer. — amit, Jun 23 '15 at 12:22
@amit It asks for an algorithm, which is the same as 'code for me'. — AStopher, Jun 23 '15 at 12:30
@cybermonkey No, it's not. Asking for algorithm is perfectly fine. [Example 1](http://stackoverflow.com/q/14415881/572670), [Example 2](http://stackoverflow.com/q/10168686/572670), [Example 3](http://stackoverflow.com/q/22342854/572670), [Example 4](http://stackoverflow.com/q/746082/572670). It's perfectly fine to ask "How to do X", and asking for an algorithm is also on topic since it can be easily translated to any programming language. you can argue that the question does not show enough research effort - but that's another question. — amit, Jun 23 '15 at 12:33

score 9 · Accepted Answer · edited Apr 27 '16 at 01:00

9

IIUC, this is the classic Minimum Vertex Cover problem, which is, unfortunately, NP Complete.

Fortunately, the most intuitive and greedy possible algorithm is as good as it gets in this case.

edited Apr 27 '16 at 01:00

nneonneo

171,345
36
312
383

answered Jun 23 '15 at 12:19

Ami Tavory

74,578
11
141
185

The "most intuitive and greedy possible algorithm is" only "as good as it gets" when [1.2738^(subset_size) time](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.432.831) is too long. – Sep 10 '16 at 22:22

score 2 · Answer 2 · answered Jun 23 '15 at 12:34

The greedy algorithm is a 2-approximation for vertex cover, which in theory, under the Unique Games Conjecture, is as good as it gets. In practice, solving a formulation of vertex cover as an integer program will most likely yield much better results. The program is

min sum_{v in V} x(v)
s.t.
forall {u, v} in E, x(u) + x(v) >= 1
forall v in V, x(v) in {0, 1}.

score 0 · Answer 3 · answered Dec 06 '15 at 16:14

Try this way:

Define a variable to count number of vertexes, starting by 0;
Create a Max-Heap of vertexes sorted by the length of the adjacent list of each vertex;
Remove all edges from the first vertex of the Heap (the one with biggest number of edges) and remove it from the Heap, adding 1 to the count;

Reorder the Heap now that number of edges of the vertexes changed, repeating the previous step until the length of the adjacent list from the first vertex is 0;

Heap Q
int count = 0

while(1){

    Q = Create_Heap(G)
    Vertex first = Q.pop
    if(first.adjacents.size() == 0) {
        break
    }

    for( Vertex v : first.adjacent ){
        RemoveEdge(first, v)
        RemoveEdge(v, first)    /* depends on the implementation */
    }

    count = count + 1

}

return count

Disconnect all vertices in a graph - Algorithm

3 Answers3