Talk:Clique (graph theory)
From Wikipedia, the free encyclopedia
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 nk 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)
