Editing Clique problem (section)

===Listing all maximal cliques===
By a result of {{harvtxt|Moon|Moser|1965}}, every {{mvar|n}}-vertex graph has at most {{math|3<sup>''n''/3</sup>}} maximal cliques. They can be listed by the [[Bron–Kerbosch algorithm]], a recursive [[backtracking]] procedure of {{harvtxt|Bron|Kerbosch|1973}}. The main recursive subroutine of this procedure has three arguments: a partially constructed (non-maximal) clique, a set of candidate vertices that could be added to the clique, and another set of vertices that should not be added (because doing so would lead to a clique that has already been found). The algorithm tries adding the candidate vertices one by one to the partial clique, making a recursive call for each one. After trying each of these vertices, it moves it to the set of vertices that should not be added again. Variants of this algorithm can be shown to have worst-case running time {{math|{{italics correction|''O''}}(3<sup>''n''/3</sup>)}}, matching the number of cliques that might need to be listed.{{sfnp|Tomita|Tanaka|Takahashi|2006}} Therefore, this provides a worst-case-optimal solution to the problem of listing all maximal cliques. Further, the Bron–Kerbosch algorithm has been widely reported as being faster in practice than its alternatives.<ref>{{harvtxt|Cazals|Karande|2008}}; {{harvtxt|Eppstein|Löffler|Strash|2013}}.</ref>

However, when the number of cliques is significantly smaller than its worst case, other algorithms might be preferable. As {{harvtxt|Tsukiyama|Ide|Ariyoshi|Shirakawa|1977}} showed, it is also possible to list all maximal cliques in a graph in an amount of time that is polynomial per generated clique. An algorithm such as theirs in which the running time depends on the output size is known as an [[output-sensitive algorithm]]. Their algorithm is based on the following two observations, relating the maximal cliques of the given graph {{mvar|G}} to the maximal cliques of a graph {{math|''G''&nbsp;\&nbsp;''v''}} formed by removing an arbitrary vertex {{mvar|v}} from {{mvar|G}}:
*For every maximal clique {{mvar|K}} of {{math|''G''&nbsp;\&nbsp;''v''}}, either {{mvar|K}} continues to form a maximal clique in {{mvar|G}}, or {{math|''K''&nbsp;⋃&nbsp;{''v''} }} forms a maximal clique in {{mvar|G}}. Therefore, {{mvar|G}} has at least as many maximal cliques as {{math|''G''&nbsp;\&nbsp;''v''}} does.
*Each maximal clique in {{mvar|G}} that does not contain {{mvar|v}} is a maximal clique in {{math|''G''&nbsp;\&nbsp;''v''}}, and each maximal clique in {{mvar|G}} that does contain {{mvar|v}} can be formed from a maximal clique {{mvar|K}} in {{math|''G''&nbsp;\&nbsp;''v''}} by adding {{mvar|v}} and removing the non-neighbors of {{mvar|v}} from {{mvar|K}}.
Using these observations they can generate all maximal cliques in {{mvar|G}} by a recursive algorithm that chooses a vertex {{mvar|v}} arbitrarily and then, for each maximal clique {{mvar|K}} in {{math|''G''&nbsp;\&nbsp;''v''}}, outputs both {{mvar|K}} and the clique formed by adding {{mvar|v}} to {{mvar|K}} and removing the non-neighbors of {{mvar|v}}. However, some cliques of {{mvar|G}} may be generated in this way from more than one parent clique of {{math|''G''&nbsp;\&nbsp;''v''}}, so they eliminate duplicates by outputting a clique in {{mvar|G}} only when its parent in {{math|''G''&nbsp;\&nbsp;''v''}} is lexicographically maximum among all possible parent cliques. On the basis of this principle, they show that all maximal cliques in {{mvar|G}} may be generated in time {{math|{{italics correction|''O''}}(''mn'')}} per clique, where {{mvar|m}} is the number of edges in {{mvar|G}} and {{mvar|n}} is the number of vertices. {{harvtxt|Chiba|Nishizeki|1985}} improve this to {{math|O(''ma'')}} per clique, where {{mvar|a}} is the arboricity of the given graph. {{harvtxt|Makino|Uno|2004}} provide an alternative output-sensitive algorithm based on fast matrix multiplication. {{harvtxt|Johnson|Yannakakis|1988}} show that it is even possible to list all maximal cliques in [[lexicographic order]] with [[polynomial delay]] per clique. However, the choice of ordering is important for the efficiency of this algorithm: for the reverse of this order,
there is no polynomial-delay algorithm unless [[P = NP]].

On the basis of this result, it is possible to list all maximal cliques in polynomial time, for families of graphs in which the number of cliques is polynomially bounded. These families include [[chordal graph]]s, [[complete graph]]s, [[triangle-free graph]]s, [[interval graph]]s, graphs of bounded [[boxicity]], and [[planar graph]]s.{{sfnp|Rosgen|Stewart|2007}} In particular, the planar graphs have {{math|{{italics correction|''O''}}(''n'')}} cliques, of at most constant size, that can be listed in linear time. The same is true for any family of graphs that is both [[dense graph|sparse]] (having a number of edges at most a constant times the number of vertices) and [[Closure (mathematics)|closed]] under the operation of taking subgraphs.<ref name="CN85"/><ref name="ELS10"/>