1
$\begingroup$

Consider the problem $\frac{n}{3}$-CLIQUE: determining whether a graph contains a clique with at least $n/3$ vertices.

I want to prove it is NP-complete using a polynomial transformation from CLIQUE.

How can I approach this problem?

$\endgroup$
  • 2
    $\begingroup$ 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. Apr 15 at 5:39
  • 2
    $\begingroup$ What did you try? $\endgroup$ – Noname Apr 15 at 10:15
3
$\begingroup$

Let me explain how to solve this, leaving all details to you.

Given an instance $(G,k)$ of CLIQUE, we want to construct an equivalent instance of $\frac{n}{3}$-CLIQUE, say $G'$. Let us denote by $|G|$ the number of vertices in $G$. There are several cases to consider:

  • Case 1: $k = |G|/3$. In this case you can take $G' = G$.
  • Case 2: $k > |G|/3$. In this case you want to increase the number of vertices to $3k$ without changing the size of the maximum clique.
  • Case 3: $k < |G|/3$. This is the most complicated case. You want to increase the number of vertices to some $n'$ while increasing the size of the maximum clique by some $\Delta$. You are done if you can ensure that $k+\Delta = n'/3$. (In fact, it suffices to have $k+\Delta > n'/3$, since then we can use Case 2.)

You take it from here.

| cite | improve this answer | |
$\endgroup$
-2
$\begingroup$

I'do go for the approach of assuming that it is solvable in polynomial time, then proving that given this solution u can reach the solution of the general Clique problem in polynomial time. So it is only polynomial if P=NP -i.e., simply prove the 2nd part, think if someone gave u a black box to get n/3 CLIQUE how can u use it to get the general CLIQUE

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Some people gave minus to this approach without discussion. I really have a lot of headache & high pressure these days to dig into it more, but THERE ARE papers that get the MWIS by applying min-cut, getting smaller indep. sets, then merge the resulting solution somehow. You can apply the same idea here to find out the complexity of getting the max clique from solving the smaller n/3 problem. I wonder who exactly gives a score to a certain answer? Or even worse delete/edit? Don't u know the principle of preventing readups & write downs to avoid trojan horses? $\endgroup$ – ShAr Apr 25 at 13:12

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.