Editing Clique problem (section)

==Lower bounds==

===NP-completeness===
[[File:Sat reduced to Clique from Sipser.svg|thumb|The 3-CNF Satisfiability instance (x ∨ x ∨ y) ∧ (~x ∨ ~y ∨ ~y) ∧ (~x ∨ y ∨ y) reduced to Clique. The green vertices form a 3-clique and correspond to a satisfying assignment.<ref>Adapted from {{harvtxt|Sipser|1996}}</ref>]]
The clique decision problem is [[NP-complete]]. It was one of [[Karp's 21 NP-complete problems|Richard Karp's original 21 problems]] shown NP-complete in his 1972 paper "Reducibility Among Combinatorial Problems".{{sfnp|Karp|1972}}  This problem was also mentioned in [[Stephen Cook]]'s paper introducing the theory of NP-complete problems.{{sfnp|Cook|1971}} Because of the hardness of the decision problem, the problem of finding a maximum clique is also NP-hard. If one could solve it, one could also solve the decision problem, by comparing the size of the maximum clique to the size parameter given as input in the decision problem.

Karp's NP-completeness proof is a [[many-one reduction]] from the [[Boolean satisfiability problem]]. It describes how to translate Boolean formulas in [[conjunctive normal form]] (CNF) into equivalent instances of the maximum clique problem.<ref>{{harvtxt|Cook|1971}} gives essentially the same reduction, from [[3-SAT]] instead of Satisfiability, to show that [[subgraph isomorphism]] is NP-complete.</ref> Satisfiability, in turn, was proved NP-complete in the [[Cook–Levin theorem]]. From a given CNF formula, Karp forms a graph that has a vertex for every pair {{math|(''v'',''c'')}}, where {{mvar|v}} is a variable or its negation and {{mvar|c}} is a clause in the formula that contains {{mvar|v}}. Two of these vertices are connected by an edge if they represent compatible variable assignments for different clauses. That is, there is an edge from {{math|(''v'',''c'')}} to {{math|(''u'',''d'')}} whenever {{math|''c''&nbsp;≠&nbsp;''d''}} and {{mvar|u}} and {{mvar|v}} are not each other's negations. If {{mvar|k}} denotes the number of clauses in the CNF formula, then the {{mvar|k}}-vertex cliques in this graph represent consistent ways of assigning [[truth values]] to some of its variables in order to satisfy the formula. Therefore, the formula is satisfiable if and only if a {{mvar|k}}-vertex clique exists.{{sfnp|Karp|1972}}

Some NP-complete problems (such as the [[travelling salesman problem]] in [[planar graph]]s) may be solved in time that is exponential in a sublinear function of the input size parameter {{mvar|n}}, significantly faster than a brute-force search.<ref>{{harvtxt|Lipton|Tarjan|1980}}.</ref> However, it is unlikely that such a subexponential time bound is possible for the clique problem in arbitrary graphs, as it would imply similarly subexponential bounds for many other standard NP-complete problems.{{sfnp|Impagliazzo|Paturi|Zane|2001}}

===Circuit complexity===
[[File:Monotone circuit for 3-clique.svg|thumb|A monotone circuit to detect a {{mvar|k}}-clique in an {{mvar|n}}-vertex graph for {{math|1=''k''&nbsp;=&nbsp;3}} and {{math|1=''n''&nbsp;=&nbsp;4}}. Each input to the circuit encodes the presence or absence of a particular (red) edge in the graph. The circuit uses one internal and-gate to detect each potential {{mvar|k}}-clique.]]
The computational difficulty of the clique problem has led it to be used to prove several lower bounds in [[circuit complexity]]. The existence of a clique of a given size is a [[Hereditary property|monotone graph property]], meaning that, if a clique exists in a given graph, it will exist in any [[Glossary of graph theory terms#supergraph|supergraph]]. Because this property is monotone, there must exist a monotone circuit, using only [[and gate]]s and [[or gate]]s, to solve the clique decision problem for a given fixed clique size. However, the size of these circuits can be proven to be a super-polynomial function of the number of vertices and the clique size, exponential in the cube root of the number of vertices.<ref>{{harvtxt|Alon|Boppana|1987}}. For earlier and weaker bounds on monotone circuits for the clique problem, see {{harvtxt|Valiant|1983}} and {{harvtxt|Razborov|1985}}.</ref> Even if a small number of [[NOT gate]]s are allowed, the complexity remains superpolynomial.<ref>{{harvtxt|Amano|Maruoka|2005}}.</ref> Additionally, the depth of a monotone circuit for the clique problem using gates of bounded [[fan-in]] must be at least a polynomial in the clique size.<ref>{{harvtxt|Goldmann|Håstad|1992}} used [[communication complexity]] to prove this result.</ref>

===Decision tree complexity===

[[File:Decision tree for 3-clique no arrowheads.svg|thumb|A simple decision tree to detect the presence of a 3-clique in a 4-vertex graph. It uses up to 6 questions of the form "Does the red edge exist?", matching the optimal bound ''n''(''n''&nbsp;&minus;&nbsp;1)/2.]]
The (deterministic) [[decision tree complexity]] of determining a [[graph property]] is the number of questions of the form "Is there an edge between vertex {{mvar|u}} and vertex {{mvar|v}}?" that have to be answered in the worst case to determine whether a graph has a particular property. That is, it is the minimum height of a Boolean [[Decision tree model|decision tree]] for the problem. There are {{math|''n''(''n''&nbsp;&minus;&nbsp;1)/2}} possible questions to be asked. Therefore, any graph property can be determined with at most {{math|''n''(''n''&nbsp;&minus;&nbsp;1)/2}} questions. It is also possible to define random and quantum decision tree complexity of a property, the expected number of questions (for a worst case input) that a randomized or quantum algorithm needs to have answered in order to correctly determine whether the given graph has the property.<ref>See {{harvtxt|Arora|Barak|2009}}, Chapter 12, "Decision trees", pp. 259–269.</ref>

Because the property of containing a clique is monotone, it is covered by the [[Aanderaa–Karp–Rosenberg conjecture]], which states that the deterministic decision tree complexity of determining any non-trivial monotone graph property is exactly {{math|''n''(''n''&nbsp;&minus;&nbsp;1)/2}}. For arbitrary monotone graph properties, this conjecture remains unproven. However, for deterministic decision trees, and for any {{mvar|k}} in the range {{math|2 ≤ ''k'' ≤ ''n''}},  the property of containing a {{mvar|k}}-clique was shown to have decision tree complexity exactly {{math|''n''(''n''&nbsp;&minus;&nbsp;1)/2}} by {{Harvtxt|Bollobás|1976}}. Deterministic decision trees also require exponential size to detect cliques, or large polynomial size to detect cliques of bounded size.<ref>{{harvtxt|Wegener|1988}}.</ref>

The Aanderaa–Karp–Rosenberg conjecture also states that the randomized decision tree complexity of non-trivial monotone functions is {{math|Θ(''n''<sup>2</sup>)}}. The conjecture again remains unproven, but has been resolved for the property of containing a {{mvar|k}} clique for {{math|2 ≤ ''k'' ≤ ''n''}}. This property is known to have randomized decision tree complexity {{math|Θ(''n''<sup>2</sup>)}}.<ref>For instance, this follows from {{Harvtxt|Gröger|1992}}.</ref> For quantum decision trees, the best known lower bound is {{math|Ω(''n'')}}, but no matching algorithm is known for the case of {{math|''k'' ≥ 3}}.<ref>{{harvtxt|Childs|Eisenberg|2005}}; {{harvtxt|Magniez|Santha|Szegedy|2007}}.</ref>

===Fixed-parameter intractability===
[[Parameterized complexity]] is the [[computational complexity theory|complexity-theoretic]] study of problems that are naturally equipped with a small integer parameter {{mvar|k}} and for which the problem becomes more difficult as {{mvar|k}} increases, such as finding {{mvar|k}}-cliques in graphs. A problem is said to be fixed-parameter tractable if there is an algorithm for solving it on inputs of size {{mvar|n}}, and a function {{mvar|f}}, such that the algorithm runs in time {{math|''f''(''k'')&nbsp;''n''<sup>{{italics correction|''O''}}(1)</sup>}}. That is, it is fixed-parameter tractable if it can be solved in polynomial time for any fixed value of {{mvar|k}} and moreover if the exponent of the polynomial does not depend on {{mvar|k}}.<ref>{{harvtxt|Downey|Fellows|1999}}. Technically, there is usually an additional requirement that {{mvar|f}} be a [[computable function]].</ref>

For finding {{mvar|k}}-vertex cliques, the brute force search algorithm has running time {{math|O(''n''<sup>''k''</sup>''k''<sup>2</sup>)}}. Because the exponent of {{mvar|n}} depends on {{mvar|k}}, this algorithm is not fixed-parameter tractable.
Although it can be improved by fast [[matrix multiplication]], the running time still has an exponent that is linear in {{mvar|k}}. Thus, although the running time of known algorithms for the clique problem is polynomial for any fixed {{mvar|k}}, these algorithms do not suffice for fixed-parameter tractability. {{harvtxt|Downey|Fellows|1995}} defined a hierarchy of parametrized problems, the W hierarchy, that they conjectured did not have fixed-parameter tractable algorithms. They proved that independent set (or, equivalently, clique) is hard for the first level of this hierarchy, [[W(1)|W[1]]]. Thus, according to their conjecture, clique has no fixed-parameter tractable algorithm. Moreover, this result provides the basis for proofs of W[1]-hardness of many other problems, and thus serves as an analogue of the [[Cook–Levin theorem]] for parameterized complexity.{{sfnp|Downey|Fellows|1995}}

{{harvtxt|Chen|Huang|Kanj|Xia|2006}} showed that finding {{mvar|k}}-vertex cliques cannot be done in time {{math|''n''<sup>''o''(''k'')</sup>}} unless the [[exponential time hypothesis]] fails. Again, this provides evidence that no fixed-parameter tractable algorithm is possible.{{sfnp|Chen|Huang|Kanj|Xia|2006}}

Although the problems of listing maximal cliques or finding maximum cliques are unlikely to be fixed-parameter tractable with the parameter {{mvar|k}}, they may be fixed-parameter tractable for other parameters of instance complexity. For instance, both problems are known to be fixed-parameter tractable when parametrized by the [[degeneracy (graph theory)|degeneracy]] of the input graph.<ref name="ELS10">{{harvtxt|Eppstein|Löffler|Strash|2013}}.</ref>

===Hardness of approximation===
[[File:Cube-face-intersection-graph.svg|thumb|A graph of compatibility relations among 2-bit samples of 3-bit proof strings. Each maximal clique (triangle) in this graph represents all ways of sampling a single 3-bit string. The proof of inapproximability of the clique problem involves [[induced subgraph]]s of analogously defined graphs for larger numbers of bits.]]
Weak results hinting that the clique problem might be hard to approximate have been known for a long time. {{harvtxt|Garey|Johnson|1978}} observed that, because the clique number takes on small integer values and is NP-hard to compute, it cannot have a [[Polynomial-time approximation scheme|fully polynomial-time approximation scheme]], unless P&nbsp;=&nbsp;NP. If too accurate an approximation were available, rounding its value to an integer would give the exact clique number. However, little more was known until the early 1990s, when several authors began to make connections between the approximation of maximum cliques and [[probabilistically checkable proof]]s. They used these connections to prove [[hardness of approximation]] results for the maximum clique problem.<ref>{{harvtxt|Feige|Goldwasser|Lovász|Safra|1991}}; {{harvtxt|Arora|Safra|1998}}; {{harvtxt|Arora|Lund|Motwani|Sudan|1998}}.</ref>
After many improvements to these results it is now known that, for every [[real number]] {{math|''ε''&nbsp;>&nbsp;0}}, there can be no polynomial time algorithm that approximates the maximum clique to within a factor better than {{math|{{italics correction|''O''}}(''n''<sup>1&nbsp;&minus;&nbsp;''ε''</sup>)}}, unless [[P versus NP problem|P = NP]].<ref>{{harvtxt|Håstad|1999}} showed inapproximability for this ratio using a stronger complexity theoretic assumption, the inequality of [[NP (complexity)|NP]] and [[ZPP (complexity)|ZPP]]. {{harvtxt|Khot|2001}} described more precisely the inapproximability ratio, but with an even stronger assumption. {{harvtxt|Zuckerman|2006}} [[derandomization|derandomized]] the construction weakening its assumption to P&nbsp;≠&nbsp;NP.</ref>

The rough idea of these inapproximability results is to form a graph that represents a probabilistically checkable proof system for an NP-complete problem such as the Boolean satisfiability problem. In a probabilistically checkable proof system, a proof is represented as a sequence of bits. An instance of the satisfiability problem should have a valid proof if and only if it is satisfiable. The proof is checked by an algorithm that, after a polynomial-time computation on the input to the satisfiability problem, chooses to examine a small number of randomly chosen positions of the proof string. Depending on what values are found at that sample of bits, the checker will either accept or reject the proof, without looking at the rest of the bits. False negatives are not allowed: a valid proof must always be accepted. However, an invalid proof may sometimes mistakenly be accepted. For every invalid proof, the probability that the checker will accept it must be low.<ref name="inapprox-redux"/>

To transform a probabilistically checkable proof system of this type into a clique problem, one forms a graph with a vertex for each possible accepting run of the proof checker. That is, a vertex is defined by one of the possible random choices of sets of positions to examine, and by bit values for those positions that would cause the checker to accept the proof. It can be represented by a [[partial word]] with a 0 or 1 at each examined position and a [[wildcard character]] at each remaining position. Two vertices are adjacent, in this graph, if the corresponding two accepting runs see the same bit values at every position they both examine. Each (valid or invalid) proof string corresponds to a clique, the set of accepting runs that see that proof string, and all maximal cliques arise in this way. One of these cliques is large if and only if it corresponds to a proof string that many proof checkers accept. If the original satisfiability instance is satisfiable, it will have a valid proof string, one that is accepted by all runs of the checker, and this string will correspond to a large clique in the graph. However, if the original instance is not satisfiable, then all proof strings are invalid, each proof string has only a small number of checker runs that mistakenly accept it, and all cliques are small. Therefore, if one could distinguish in polynomial time between graphs that have large cliques and graphs in which all cliques are small, or if one could accurately approximate the clique problem, then applying this approximation to the graphs generated from satisfiability instances would allow satisfiable instances to be distinguished from unsatisfiable instances. However, this is not possible unless P&nbsp;=&nbsp;NP.<ref name="inapprox-redux">This reduction is originally due to {{harvtxt|Feige|Goldwasser|Lovász|Safra|1991}} and used in all subsequent inapproximability proofs; the proofs differ in the strengths and details of the probabilistically checkable proof systems that they rely on.</ref>
{{Clear}}