Is there an algorithm for finding minimal covers of a set of sets in which each element of the universe appears in exactly 2 sets? I realize that LP relaxation approximates this to within a factor of 2.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
9
This is the well-known problem of Minimum Vertex Cover. It is conjectured to be NP-hard to approximate within $2-\epsilon$ for any $\epsilon > 0$. Many $2$-approximation algorithms exist.
-
$\begingroup$ I believe The minimum vertex cover problem is equivalent to the maximum clique problem. $\endgroup$ Commented Apr 17, 2016 at 23:09
-
$\begingroup$ Not in terms of approximability. Vertex cover is much easier. Maximum clique cannot be approximated to within $O(n^{1-\epsilon})$. $\endgroup$ Commented Apr 17, 2016 at 23:13
-
$\begingroup$ Has this been proven or is this simply the best current approximation? $\endgroup$ Commented Apr 17, 2016 at 23:30
-
$\begingroup$ Because I believe I have found an n^2 running time transformation from the maximum clique problem to the Vertex Cover Problem. $\endgroup$ Commented Apr 17, 2016 at 23:42
-
$\begingroup$ Woah, never mind. Apparently, unless P = NP, there is no approximation algorithm better than O(n^(1−ϵ)) $\endgroup$ Commented Apr 18, 2016 at 0:09