Talk:Clique problem
From Wikipedia, the free encyclopedia
I thought a clique was a fully connected sub-graph? The way it is described here makes me think a clique is two adjacent vertices... --Bryanlharris 19:21, May 7, 2004 (UTC)
- Pairwise adjacent means every pair of vertices in the set are adjacent. This is equivalent to your definition. Deco 19:38, 26 Mar 2005 (UTC)
Contents |
[edit] Proposed move
I propose we move this to maximum clique problem, which is a commonly used name that is more accurate and specific. I put a redirect in the way, but I'll take care of the move if there's consent. Deco 23:58, 27 May 2005 (UTC)
Seems like a reasonable idea. MathMartin 09:05, 28 May 2005 (UTC)
[edit] Removed proof
I removed the proof that maximum clique is NP-complete and replaced it by an appeal to the NP-completeness of independent set. It was a good proof, but I think it's easier to go through independent set, because there's a lot less edges to talk about filling in. Admittedly the proof on independent set problem isn't all that nice, and any improvement to it would be great. Deco 01:49, 8 Jun 2005 (UTC)
- Rewrote independent set problem now. Should be somewhat better. Deco 04:47, 8 Jun 2005 (UTC)
[edit] Algorithm feedback
I suggest a algorithm here. http://insaint03.cafe24.com/clique-en.html I can't be sure it's correct, I need some comment. --insaint 18:36, 26 May 2007 (UTC)
- The problem is proven NP-complete, your algorithm runs in O(n^3) - either you deserve $1million prize or the algorithm is wrong. You might try on one of the larger examples given in the link at the bottom of the article and see whether you find the known answer.
[edit] Reference
Can anyone find a source for the 3-clique algorithm mentioned in version 111018197?
Some special cases may be solved in less than exponential time. For k = 3, there exists an O(n1.41) algorithm where n is the number of edges.
-- Rampion (talk) 15:27, 16 February 2008 (UTC)
- I'm going to go ahead and remove it for now. If anyone wants to restore it, please note the reference. -- Rampion (talk) 15:00, 19 February 2008 (UTC)
[edit] Problem with maximal clique heuristic
This section seems to state that arbitrarily merging cliques will always find a maximal (as opposed to maximum) clique. This is not true. Consider 2 disjoint cliques A and B produced by merging. Assume that there is some edge missing between A and B so that they cannot be merged, but that there are vertices u in A and v in B such that u is adjacent to every vertex in B and v is adjacent to every vertex in A. Then A is contained in A union v and B is contained in B union u, so neither are maximal, but no further merging can be done. Merging in some intelligent order may work, but the algorithm as stated does not necessarily find any maximal cliques. Bjoeris (talk) 16:07, 17 April 2008 (UTC)
