0
$\begingroup$

I have been studying NP-Complete problems and I saw the Dense Subgraph problem. Then I saw that they are trying to show that the problem is NP (see below quote), but I can't understand how it verifies that time is polynomial.

Problem: Dense Subgraph

Input: A graph $G$, and integers $k$ and $y$.

Output: Does $G$ contain a subgraph with exactly $k$ vertices and at least $y$ edges?

To prove Dense Subgraph is NP-complete, we show that Dense Subgraph is in NP and is NP-hard by reducing CLIQUE problem to Dense Subgraph.

Dense Subgraph is NP: the polynomial time verifier will take $(G,k,y)$ and $H = (V', E')$ as certificate and check if $H$ is a subgraph of $G$, $|V'| = k$, $|E'| \geq y$.

$\endgroup$
1
1
$\begingroup$

You are right that that doesn't prove the algorithm is polynomial, as it just gives the certificate. But it is very easy to see that (for example with a program in a C-like language, given a reasonable representation of the graphs) the check is very easy to do (is polynomial).

The part of coming up with a polynomial verifier given a reasonable certificate (i.e., proof that the problem is in $\mathsf{NP}$) is usually easy, and left as an exercise for the gentle reader.

$\endgroup$
1
  • 1
    $\begingroup$ I understand, thanks! $\endgroup$ Jul 5 at 2:35

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.