<p>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.</p>

CC BY-SA 2.5
2010-11-26T17:54:57.137Z
2010-11-26T17:54:57.137Z
Anthony Labarre
<p>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.)</p>

CC BY-SA 2.5
2010-11-28T19:01:52.260Z
2010-11-28T19:01:52.260Z
JimN
<p>It's NP-complete to find maximum cliques in <a href="http://en.wikipedia.org/wiki/Claw-free_graph" rel="nofollow">claw-free graphs</a> [Faudree, Ralph; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Claw-free graphs — A survey", Discrete Mathematics 164 (1–3): 87–147] and in <a href="http://en.wikipedia.org/wiki/String_graph" rel="nofollow">string graphs</a> [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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-11-27T05:26:58.683Z
2010-11-27T05:26:58.683Z
David Eppstein
<p>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 <a href="http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems" rel="nofollow">list</a> of 21 NP-complete problems. My question is:</p>

<blockquote>
  <p>For what restricted families of graphs is CLIQUE known to be NP-complete?</p>
</blockquote>

<p>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]. </p>

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

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

CC BY-SA 2.5
2010-11-26T17:58:29.173Z
[ISGCI](http://wwwteo.informatik.uni-rostock.de/isgci/) is your friend.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-27T02:52:51.583Z
@Tsuyoshi Ito - that's a fantastic resource, certainly worthy of answer status.
s8soj3o289
CC BY-SA 2.5
2010-11-28T21:22:40.960Z
@blackkettle: It's in the FAQ.
András Salamon
<reference-request><np-hardness><clique>
Graph classes in which CLIQUE is known to be NP-hard?
gphilip
# Graph classes in which CLIQUE is known to be NP-hard?

(Asked by: username_0 on 2010-11-26)

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](http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems) 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

**Tags:** reference-request, np-hardness, clique

> **Comments:**
> **username_1**: [ISGCI](http://wwwteo.informatik.uni-rostock.de/isgci/) is your friend.  
> **username_2**: @username_1 - that's a fantastic resource, certainly worthy of answer status.  
> **username_3**: @blackkettle: It's in the FAQ.  

---

## 3 answers

### Answer by username_6 on 2010-11-27. Score: 12 | Accepted answer

It's NP-complete to find maximum cliques in [claw-free graphs](http://en.wikipedia.org/wiki/Claw-free_graph) [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](http://en.wikipedia.org/wiki/String_graph) [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.


---

### Answer by username_4 on 2010-11-26. Score: 3

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.


---

### Answer by username_5 on 2010-11-28. Score: 2

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.)


---

