2
$\begingroup$

I am looking for NP complete results for cliques in regular graphs. For example is the general problem of determining if a regular graph on n vertices has an n/2 clique NP-complete? (obviously the question is interesting only if the degree is at least n/2). You could also ask the same question for say regular graphs of degree 3n/4.

$\endgroup$
1
  • $\begingroup$ There is lots of information (though not an answer to your exact question) at en.wikipedia.org/wiki/Clique_problem. $\endgroup$ Jun 24 '14 at 4:06
4
$\begingroup$

Let $G = (V,E)$ be a graph and $c ≤ |V |$ a positive integer. The independent sets of $G$ are precisely the cliques of the complementary graph $\overline{G}$.

INDEPENDENT SET

INSTANCE: Graph $G=(V,E)$, positive integer $c$.

QUESTION: Does $G$ contain an independent set of size $c$ or more,

The independent set problem remains NP-complete when restricted to 3-regular planar graphs.

Reference:

COMPUTERS AND Intractability, A Guide to the Theory of NP-Completeness

Michael R. Garey / David S. Johnson

page 194-195

$\endgroup$
2
  • 1
    $\begingroup$ This answers the question for cliques of specified size, but it doesn't answer it for cliques of size n/2. 3-regular graphs have an independent set of size $n/2$ iff they are bipartite. $\endgroup$ Jun 25 '14 at 19:42
  • $\begingroup$ The key is that the complement of a regular graph is regular. $\endgroup$
    – Null_Space
    Jun 28 at 13:34

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.