Does there exist a simple approximation to the minimum vertex cover problem that aims to find a smaller (or equal) set to the minimum?

Usual algorithms seems to aim to find an approximation such that the output is a cover, but may have more vertices than the minimum cover. Instead, I want a smaller set - I don't mind if some edges are still left and is therefore not a cover. Between two smaller sets, the one that covers more (total number of edges) is preferable.

  • $\begingroup$ I'm not looking for the usual approximation. I want a cover size equal or smaller than the min - so it may not be exactly a vertex-cover. I'm just looking for a heuristic, what would you do if you can't afford an exact search to get the exact min cover, but you don't want a larger cover as approximation, just something smaller. $\endgroup$ – jam123 Sep 16 '14 at 21:23
  • 2
    $\begingroup$ I can't understand what you're asking. What does "aims to find a smaller (or equal) set to the minimum" mean? The minimum size set is the minimum; there can't exist anything smaller (by definition). If you're asking for an algorithm that produces exactly the minimum, that's not an approximation algorithm, it's NP-hard. So what are you asking? You might want to edit your question to state your question more carefully. Perhaps you are asking for a set that is not necessarily a cover, but is somehow "close" to a cover? If so, you need to define what you mean by "close". $\endgroup$ – D.W. Sep 16 '14 at 22:23
  • 4
    $\begingroup$ I see you edited the question. Thank you. Unfortunately, this problem still isn't well-defined, as you haven't defined a metric (an objective function) that you want to see maximized. If I have a set of 5 vertices that covers 20 edges, and another set of 6 vertices that covers 22 edges, which one do you want the algorithm to return? If the only thing that matters is the number of edges covered, then this problem is equivalent to finding the exact solution to minimum set cover and thus NP-hard. $\endgroup$ – D.W. Sep 17 '14 at 0:08
  • 4
    $\begingroup$ If you want to maximize the number of edges covered, given a budget on the number of vertices, check out en.wikipedia.org/wiki/Maximum_coverage_problem. For general set-cover problems the greedy algorithm gives a 1-1/e approximation-algorithm. If you want to cover at least a given number k of the edges, while minimizing the number (or weight) of the vertices used to cover them, look for Partial Vertex Cover (2-approximation algorithms). If you want a lower bound on the OPT vertex cover size (or weight), all the standard 2-approximation algs for vertex cover also give a lower bound. $\endgroup$ – Neal Young Sep 18 '14 at 15:40

Do you want a set whose size is a lower bound? Or do you want a lower bound on the size?

If you want a set, does it need to be a subset of a minimum vertex cover, or just a smaller set (in the latter case, any set of the appropriate cardinality would do)?

Since there is a well-known approximation algorithm that is a factor of two over-approximation, you can divide the result by two to get a factor of two under-approximation. In fact, these notes use a lower bound to prove the over-approximation factor.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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