7
$\begingroup$

Given a graph $G$ and a positive integer $k$, the CLIQUE problem asks if $G$ contains a clique (complete subgraph) on at least $k$ vertices. This problem is long known to be NP-complete --- in fact, it was one of Karp's list of 21 NP-complete problems. My question is:

For what restricted families of graphs is CLIQUE known to be NP-complete?

I could find one such graph class with Google's help: the class of $t$-interval graphs for any $t\ge 3$ (Butman et al., TALG 2010) [1].

Do you know of other graph classes where this problem has been shown to be NP-complete?

[1] Butman, Hermelin, Lewenstein, Rawitz. Optimization problems in multiple-interval graphs. ACM Transactions on Algorithms 6(2), 2010

$\endgroup$
  • 8
    $\begingroup$ ISGCI is your friend. $\endgroup$ – Tsuyoshi Ito Nov 26 '10 at 17:58
  • $\begingroup$ @Tsuyoshi Ito - that's a fantastic resource, certainly worthy of answer status. $\endgroup$ – s8soj3o289 Nov 27 '10 at 2:52
  • 1
    $\begingroup$ @blackkettle: It's in the FAQ. $\endgroup$ – András Salamon Nov 28 '10 at 21:22
12
$\begingroup$

It's NP-complete to find maximum cliques in claw-free graphs [Faudree, Ralph; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Claw-free graphs — A survey", Discrete Mathematics 164 (1–3): 87–147] and in string graphs [Jan Kratochvíl and Jaroslav Nešetřil, INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs, Commentationes Mathematicae Universitatis Carolinae, Vol. 31 (1990), No. 1, 85–93]. At least as of the 1990 paper it was open whether the problem remained hard for intersection graphs of straight line segments.

However, finding maximum cliques easy for planar graphs, for minor-closed graph families, or more generally for any family of graphs with bounded degeneracy: find the minimum degree vertex, search for the largest clique among its O(1) neighbors, remove the vertex, and repeat. It's also easy for perfect graphs and the many important subfamilies of perfect graphs.

Although maximum independent set is hard for many other interesting graph classes, that doesn't generally lead to interesting hardness results for clique, because the complement of an interesting graph class is not necessarily itself interesting.

$\endgroup$
3
$\begingroup$

The equivalence of CLIQUE on $G$ and INDEPENDENT SET on $\overline{G}$ will perhaps help you find more classes for which the problem remains NP-complete.

$\endgroup$
2
$\begingroup$

Although this doesn't answer the question as stated (with NP-hardness) I'd like to point out that even though CLIQUE is known polytime solvable on perfect graphs, I believe it is still open to find a (non-ellipsoid-like) combinatorial algorithm for CLIQUE even on perfectly orderable graphs... (that is, a perfectly orderable graph when the perfect order is not part of the input.)

$\endgroup$

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.