How to prove that the problem VERTEX-COVER belongs to $NP$?

The problem VC is defined as follow:

INSTANCE: Graph $G = (V,E)$ and an integer $k$

PREDICATE: Is there a subset $V_1 \in V $ s.t $\mid V_1 \mid \leq k $ and $\forall (u,v) \in E $ $u \in V_1 $ or $v \in V_1$ ?

My approach:

I know that the class $NP$ can be defined as the class of all problems that can be solved using non-deterministic algorithms that runs in polynomial time.

Therefore, i can guess if $\mid V_1 \mid \leq k$ then test for each node in $E$ if $u$ or $v$ belongs to $V_1$. In this case return $TRUE$, otherwise $FALSE$.

  • $\begingroup$ For which $V_1$ do you guess whether $|V_1| \leq k$? $\endgroup$ – Yuval Filmus Nov 4 '17 at 15:25
  • $\begingroup$ For all $V_j$ i think $\endgroup$ – Jack Nov 4 '17 at 16:00
  • $\begingroup$ There are exponentially many potential $V_1$s. You want a (nondeterministic) polynomial time algorithm. $\endgroup$ – Yuval Filmus Nov 4 '17 at 16:01
  • $\begingroup$ So what about using a "Guess function" that do this task ? $\endgroup$ – Jack Nov 4 '17 at 16:06
  • $\begingroup$ The question asks you to spell out how this would work. $\endgroup$ – Yuval Filmus Nov 4 '17 at 16:07

Your Answer

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

Browse other questions tagged or ask your own question.