Maximum Clique

An NpComplete problem. Given any graph (see GraphTheory) and a number k, we ask whether there exists a subgraph with k nodes in which every node is connected to every other node.

I demonstrated a polynomial-time reduction from CLIQUE detection to PerlLanguage RegularExpression matching: http://home.hiwaay.net/~gbacon/perl/clique.html

For other reductions, visit http://perl.plover.com/NPC/

-- GregBacon

Some more stuff on NpComplete problems and clique partitioning: http://www.busygin.dp.ua/npc.html

Zohreh O. Akbari has apparently found a polynomial-time algorithm for this problem: http://www.waset.org/pwaset/v35/v35-74.pdf

-- MichaelKirsch

I take it you didn't actually read the paper? It attempts to present a greedy algorithm and justify avoidance of backtracking, and the author plays fast and loose with assumptions. The argument concluding in point (9) makes a mistake of 'exponential' proportions, ignoring that removing vertex x or y in pursuit of MNS(k) really is a branching possibility that may eliminate the need to remove 0s from Nil(k-1), and may make more optimal a different earlier decision about whether to eliminate an 'x' or 'y' in pursuit of MNS(0 <= i < k).

I read it, but I'll admit that that mistake flew right past me. I'll pass that back to the friend that pointed me at the paper in question.

CategoryMath