1
$\begingroup$

Instance: An undirected graph $G$ and a positive integer $k$

Question: Does $G$ contain a vertex cover of size $\leq k$ or a clique of size $\geq k$?

Obviously, this problem is solved by polynomial reduction, but is it from Clique or Vertex Cover? And how?

I've tried to reduce from both problems, but seem to get stuck. If I reduce from Clique, for example, It seems I'd need to guarantee that there isn't a Vertex Cover, but it's not clear to me how to do that. It seems reducing from Vertex Cover is more promising, but I run into the same issue

$\endgroup$

1 Answer 1

3
$\begingroup$

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 trivially solvable in polynomial time).

Given a graph $G$ on $n$ vertices and $3\leq k \leq n$, construct a graph $G'$ by taking the disjoint union of $G$ with a perfect matching on $2(n+1)$ additional vertices.

Now, $G$ has a clique of size $\geq k$ if and only if $G'$ has a clique of size $\geq k$. This is because if we find a clique of size $\geq k\geq 3$ in $G$ then it cannot lie in the matching part, as this has no cliques of size greater than $2$. Moreover, $G'$ has no vertex cover of size $\leq k$, as you need at least $n+1$ vertices to cover the matching. Thus, $G$ has a clique of size $k$ if and only if $G'$ has a clique of size $\geq k$ or a vertex cover of size $\leq k$ (this second condition always being false).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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