Editing Clique problem (section)

===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>