Detach all vertices in the graph - Algorithm

Question

I am looking for an algorithm that will find the minimum subset of vertices in such a way that by removing this subset (and the edges connecting these vertices) from the graph, all other vertices become disconnected (i.e. the graph will not have any edges).

• Is there such an algorithm?
• If not: could you recommend some heuristics to indicate vertices.

I have basic knowledge of graph theory, so please excuse any infidelity.

Answer 1

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

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

Answer 2

The greedy algorithm is a 2-approximation for vertex coverage, which theoretically, according to the hypothesis of unique games, is as good as it gets. In practice, solving the formulation of vertex cover as an integer program is likely to give much better results. Program

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

Answer 3

Try as follows:

• Define a variable to count the number of vertices starting at 0;
• Create a Max-Heap from vertices sorted by the length of the adjacent list of each vertex;
• Remove all edges from the first vertex of the heap (with the largest number of edges) and remove it from the heap by adding 1 to the score;

• Now change the heap order when the number of edges of the vertices has 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