New answers tagged

1 vote

Derandomization of vertex cover algorithm

Here are two possible derandomizations of the algorithm, with some caveats. One possible derandomized algorithm compute an optimal fractional solution $x^*$ to the standard linear-program (LP) ...
Neal Young's user avatar
3 votes

Prove "Vertex Cover OR Clique" is NP complete

You can easily reduce from clique as follows. First, notice that the clique problem remains NP-hard even if we restrict $k$ to lie in $3 \leq k \leq n$ (because outside this range the problem is ...
Tassle's user avatar
  • 2,522

Top 50 recent answers are included