In computational complexity theory, the clique problem is a graph-theoretical NP-complete problem. The problem was not only one of Richard Karp's original 21 problems shown NP-complete in his seminal 1972 paper "Reducibility Among Combinatorial Problems", but also was even mentioned in Cook's paper introducing the theory of NP-complete problems. As a branch of the theory of computation in computer science, computational complexity theory describes the scalability of algorithms, and the inherent difficulty in providing scalable algorithms for specific computational problems. ... A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use... One of the most important results of computational complexity theory was Stephen Cooks 1971 paper that demonstrated the first NP-complete problem, the boolean satisfiability problem. ...

A clique of size 3.

A clique in a graph is a set of pairwise adjacent vertices, or in other words, an induced subgraph which is a complete graph. In the graph at the right, vertices 1, 2 and 5 form a clique, because each has an edge to all the others. Image File history File links This is a lossless scalable vector image. ... Image File history File links This is a lossless scalable vector image. ... K5, a complete graph. ... In the mathematical field of graph theory a complete graph is a simple graph where an edge connects every pair of vertices. ...

Then, the clique problem is the problem of determining whether a graph contains a clique of at least a given size k. Once we have located k or more vertices which form a clique, it's trivial to verify that they do, which is why the clique problem is in NP. The corresponding optimization problem, the maximum clique problem, is to find the largest clique in a graph. In computational complexity theory, NP (Non-deterministic Polynomial time) is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. ... In computer science, an optimization problem is the problem to find among all feasible solutions for some problem the best one. ...

The NP-completeness of the clique problem follows trivially from the NP-completeness of the independent set problem, because there is a clique of size at least k if and only if there is an independent set of size at least k in the complement graph. This is easy to see, since if a subgraph is complete, its complement subgraph has no edges at all. In mathematics, the independent set problem (IS) is a well-known problem in graph theory and combinatorics. ... In graph theory, an independent, or stable, set in a graph G, which contains vertices V, is a set of vertices V (a subset of V) such that for every two vertices in V, there is no edge connecting the two. ... In graph theory the complement or inverse of a graph is a graph on the same vertices such that two vertices of are adjacent if and only if they are not adjacent in . ...

Algorithms

A brute force algorithm to find a clique in a graph is to examine each subgraph with at least k vertices and check to see if it forms a clique. This algorithm is polynomial if k is the number of vertices, or a constant less than this, but not if k is, say, half the number of vertices; the number of possible cliques of size k on a graph of size V is equal to . In computer science, a brute-force search consists of systematically enumerating every possible solution of a problem until a solution is found, or all possible solutions have been exhausted. ...

A heuristic is to start by considering each node to be a clique of size one, and to merge cliques into larger cliques until there are no more possible merges. Two cliques A and B may be merged if each node in clique A is adjacent to each node in clique B. This requires only linear time (linear in the number of edges), but may fail to find a large clique because two or more parts of the large clique have already been merged with nodes that are not in the clique. It does, however, find at least one maximal clique, which is a clique not contained in any larger clique. The algorithm can be implemented most efficiently using the union-find algorithm. Given a set of elements, it is often useful to break them up or partition them into a number of separate, nonoverlapping groups. ...

Some special cases may be solved in less than exponential time. For k = 3, there exists an O(n^1.41) algorithm where n is the number of edges.

See also

• Combinatorics
• Ramsey Theory
• Theorem on friends and strangers

Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. ... Ramsey theory, named for Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear. ... The friendship theorem is a mathematical theorem in an area of mathematics called Ramsey theory. ...

References

• Alon, Noga; Raphael Yuster & Uri Zwick (1998-08-09), Finding and counting given length cycles. Retrieved on 2007-02-14 
• Richard Karp. Reducibility Among Combinatorial Problems. Proceedings of a Symposium on the Complexity of Computer Computations. 1972.
• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5.  A1.2: GT19, pg.194.

1998 (MCMXCVIII) was a common year starting on Thursday of the Gregorian calendar, and was designated the International Year of the Ocean [1]. // Coated in ice, power and telephone lines sag and often break, resulting in power outages. ... August 9 is the 221st day of the year in the Gregorian Calendar (222nd in leap years), with 144 days remaining. ... 2007 (MMVII) is the current year, a common year starting on Monday of the Gregorian calendar and the Anno Domini (common) era. ... February 14 is the 45th day of the year in the Gregorian calendar. ... Michael R. Garey is a computer science researcher, and co-author (with David S. Johnson) of Computers and Intractibility: A Guide to the Theory of NP-completeness. ... David S. Johnson (born December 9, 1945) is a computer scientist specializing in algorithms and optimization. ...

External links

• Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring