patternMinor
minimum vertex set removal for edge-free graph
Viewed 0 times
removalgraphvertexfreeminimumedgeforset
Problem
I'd like to know the name and the algorithm for the following problem which I'm guessing is a classic, but is slightly different from graph connectivity.
Consider a undirected graph G=(V,E). What is the minimum number of vertices which removal (vertices and their adjacent edges) makes the resulting sub-graph empty of any edge?
For example:
If A - B - C, then just need to remove B.
If A - B - C and A - C, then need to remove at two vertices (any pair).
For an algo, intuitively I'd proceed by removing first the vertex of highest degree and proceed the same on the remaining graph until there are no edges. Not sure if it gives the min number. For sure, in the worst case I can always go through all possible |V|! removal possibilities and take the min.
Consider a undirected graph G=(V,E). What is the minimum number of vertices which removal (vertices and their adjacent edges) makes the resulting sub-graph empty of any edge?
For example:
If A - B - C, then just need to remove B.
If A - B - C and A - C, then need to remove at two vertices (any pair).
For an algo, intuitively I'd proceed by removing first the vertex of highest degree and proceed the same on the remaining graph until there are no edges. Not sure if it gives the min number. For sure, in the worst case I can always go through all possible |V|! removal possibilities and take the min.
Solution
The problem you describe is called minimum vertex cover. It is a well-known NP-complete problem, so there is no known algorithm that will always be fast (as in polynomial runtime) and give the optimal solution. However, fast approximation solutions are known, as well as algorithms that, while slow in the worst case on general graphs, are fast on significant classes of graphs. See the linked Wikipedia article for details and links to even more details.
Context
StackExchange Computer Science Q#30057, answer score: 5
Revisions (0)
No revisions yet.