0
$\begingroup$

I want to show that there is a polynomial-time reduction from the standard $\text{Clique}$ problem to the $\text{N-Degree-Clique}$ problem, where: $$ \text{N-Degree-Clique} = \{ \langle G, k\rangle: \text{$G$ has a clique of size $\geq k$,} \\ \text{and every vertex of $G$ has degree at least N} \}$$

I am not sure how to map the last condition and could use help figuring out a reduction.

$\endgroup$
1
  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$
    – D.W.
    Jan 6, 2021 at 19:33

1 Answer 1

1
$\begingroup$

One almost correct reduction looks like: consider the graph $G'$ that is obtained by adding $N$ new vertices to the input graph $G$. Also, add edges that connect every new vertex to all the vertices in $G$. Its not hard to show that $G$ has a clique of size at least $k$ iff $G'$ has a clique of size at least $k+1$. Note that the degree of each new vertex equals the number of vertices of $G$, which not necessarily at least $N$. But this is a minor issue that I leave for you to fix (along with proving correctness).

$\endgroup$

Your Answer

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

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