0
$\begingroup$

It's known that: $$ \textrm{CLIQUE} = \{(G,k): \mbox{G has a clique of size } k\} $$ is $\textrm{NP-C}$, but what if every vertex has 2 neighbours (as defined in $\textrm{2d-CLIQUE}$)? $$ \textrm{2d-CLIQUE} = \{(G,k): \mbox{every vertex in G has exactly $2$ neighbours and $G$ has a clique of size } k\}. $$

$\endgroup$
2
$\begingroup$

Assuming that every vertex of $G$ has degree $2$, no clique of $G$ can have more than $3$ vertices. Then $\textrm{2d-CLIQUE}$ is trivially in $\textrm{P}$ and, if $\textrm{P} \neq \textrm{NP}$, it cannot be $\textrm{NP}$-complete.

Under the above assumption (which is trivial to check), $(G,k) \in \textrm{2d-CLIQUE}$ iff one of the following conditions holds:

  • $k=0$, or
  • $k \in \{1,2\}$ and $G$ is not empty, or
  • $k = 3$ and $G$ has a triangle, which can be checked in $O(n)$ time.
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ ok, and what about 3d-CLIQUE? $\endgroup$ – Gilad Deutsch Mar 11 at 16:30
  • $\begingroup$ For any constant $h \ge 0$, $h\textrm{d-CLIQUE}$ is in $\textrm{P}$. If $k>h+1$ there can be no $k$-clique. If $k \le h+1$ you can then enumerate all the $O(n^k) = O(n^{h+1}) = n^{O(1)}$ subsets of $k$ vertices of $V$ and check in $O(h^2)$ time each if they induce a clique. In fact this even works for $\textrm{CLIQUE}$ if $k = O(1)$. $\endgroup$ – Steven Mar 11 at 16:37

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.