Talk:Clique (graph theory)

Untitled

Should be a disambiguation page with Clique (social group). --Daniel C. Boyer 20:09, 20 Apr 2004 (UTC)

---

The clique problem refers to the problem of finding the largest clique in any graph G. This problem is NP-complete,

I think there is a confusion here between the "clique problem", which is NP-complete, and the "maximum clique problem", which is not NP, AFAIK. --Marx Gomes 18:09, 7 Nov 2004 (UTC)

---

A k-clique can be found using a brute-force algorithm in O(nk) time.

This makes no sense. In the link on the previous sentence ( here ) it says that k-clique is NP-complete. So how could it have a polynomial time algorithm? Can anyone explain this? Averisk 02:35, 13 November 2005 (UTC)

It depends on whether k is part of the input; if it is, then n^k is exponential. But this doesn't really have to be explained under this lemma, which is graph theoretic and not complexity theoretic, so I'll just remove it. --Mellum 12:03, 13 November 2005 (UTC)

---

This is equivalent to saying that the subgraph induced by V is a complete graph.

Isn't this supposed to say "...the subgraph induced by E on V is a complete graph.? How does the set of vertices induce a subgraph? Nortexoid 20:25, 6 March 2006 (UTC)

how many triangles?

i remember in math class getting one of these and being asked how many triangles. i think the answer was 96! (but i don't know why i remember that??) Newtowiki2 (talk) 01:01, 15 February 2008 (UTC)

NP-complete

Finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete.

This is wrong. If the size of the clique is given (so it is a fixed value) it is not NP-complete. If you have an algorithm which gets the graph and k (=size of the clique) as input, it could solve this problem in polynomial time.

Only the problem to find the largest clique (now the size of the clique is a variable) is NP-complete.

--143.205.215.18 (talk) 09:33, 3 June 2008 (UTC)

If the size is given as part of the input (thus, a variable, not as a constant), it's still NP-complete. It's only when the size is fixed before the input is given that it can be solved in polynomial time. So it would be wrong if the word "given" were replaced by the word "fixed", but is correct as written. —David Eppstein (talk) 14:45, 3 June 2008 (UTC)

Cliques in multigraphs

A clique is defined as a subset of its vertices such that every two vertices in the subset are connected by a single edge. In a multigraph there can be multiple edges between vertices, so do cliques generalise to multigraphs such that a clique in a multigraph is defined as every two vertices connected by at least n edges? Is that worth mentioning in this article or is it better suited in the multigraphs article? pgr94 (talk) 14:11, 3 June 2010 (UTC)

Or maybe a clique is a subgraph rather than a subset of vertices, so you have to choose which one of the multiple edges to use? We would need a source that provides a clear definition. —David Eppstein (talk) 15:44, 3 June 2010 (UTC)

How to pronounce?

Is it "click"? someone should add something about how it is pronounced. — Preceding unsigned comment added by 75.59.221.42 (talk) 19:46, 7 November 2011 (UTC)

Notation V(G)

In the Definitions section, we read:

The clique cover number of a graph G is the smallest number of cliques of G whose union covers V(G).

However, V(G) is nowhere defined or explained in the article. In this context, the intent seems to be to identify the set of vertices V of the graph G = (V,E), so I'm editing the definition to read instead:

The clique cover number of a graph G is the smallest number of cliques of G whose union covers the set of vertices V of the graph.

Please improve these definitions if necessary. yoyo (talk) 14:01, 4 November 2017 (UTC)