3
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$
    – FrankW
    Sep 16, 2014 at 13:39
  • $\begingroup$ Can you clarify what you mean by "makes the resulting sub-graph empty of any edge?" Do you mean, the minimum number of vertices whose removal leaves a graph with no remaining edges? $\endgroup$
    – D.W.
    Sep 16, 2014 at 22:36

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Perfect, that article covers it. $\endgroup$
    – jam123
    Sep 16, 2014 at 13:53
  • $\begingroup$ Are you aware of an (fast) approximation of the min vertex cover with some guarantees on the approximation cover being not too large? Ideally, a guarantee that the approximate cover is smaller than the min cover - which I'm guessing is not usually the aim of approximation, but in my case I prefer a smaller cover that might still leave a few edges. $\endgroup$
    – jam123
    Sep 16, 2014 at 15:46
  • $\begingroup$ To clarify, I mean an approximation that returns either a minimum cover (ideal) or a smaller cover, not larger. $\endgroup$
    – jam123
    Sep 16, 2014 at 15:54
  • 1
    $\begingroup$ I don't know one off the top of my head. But it would be perfectly appropriate (and sensible), if you asked this as a new question, if you can't find anything yourself. (Just make sure, the answer isn't easily found by using a search engine.) $\endgroup$
    – FrankW
    Sep 16, 2014 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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