Clique problem

<h2 id="history-and-applications">History and applications</h2>
The study of complete subgraphs in mathematics predates the "clique" terminology. For instance, complete subgraphs make an early appearance in the mathematical literature in the graph-theoretic reformulation of <a href="/facts/Ramsey_theory/CzLLM2j8">Ramsey theory</a> by Erdős & Szekeres (1935). But the term "clique" and the problem of algorithmically listing cliques both come from the social sciences, where complete subgraphs are used to model <a href="/facts/Clique/udmBpXLC">social cliques</a>, groups of people who all know each other. Luce & Perry (1949) used graphs to model social networks, and adapted the social science terminology to graph theory. They were the first to call complete subgraphs "cliques". The first algorithm for solving the clique problem is that of Harary & Ross (1957),<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> who were motivated by the sociological application. Social science researchers have also defined various other types of cliques and maximal cliques in social network, "cohesive subgroups" of people or actors in the network all of whom share one of several different kinds of connectivity relation. Many of these generalized notions of cliques can also be found by constructing an undirected graph whose edges represent related pairs of actors from the social network, and then applying an algorithm for the clique problem to this graph.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>
Since the work of Harary and Ross, many others have devised algorithms for various versions of the clique problem.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> In the 1970s, researchers began studying these algorithms from the point of view of <a href="/facts/Worst-case_analysis/9lDvDaCf">worst-case analysis</a>. See, for instance, Tarjan & Trojanowski (1977), an early work on the worst-case complexity of the maximum clique problem. Also in the 1970s, beginning with the work of Cook (1971) and Karp (1972), researchers began using the theory of <a href="/facts/NP-complete/NFPv56DU">NP-completeness</a> and related intractability results to provide a mathematical explanation for the perceived difficulty of the clique problem. In the 1990s, a breakthrough series of papers beginning with Feige et al. (1991) showed that (assuming <a href="/facts/P_%E2%89%A0_NP/xoC7Ruda">P ≠ NP</a>) it is not even possible to <a href="/facts/Approximation_algorithm/BWlf7M32">approximate</a> the problem accurately and efficiently.
Clique-finding algorithms have been used in <a href="/facts/Chemistry/SrNqkGVm">chemistry</a>, to find chemicals that match a target structure<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> and to model <a href="/facts/Docking_(molecular)/IKzf94wQ">molecular docking</a> and the binding sites of chemical reactions.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> They can also be used to find similar structures within different molecules.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> In these applications, one forms a graph in which each vertex represents a matched pair of atoms, one from each of two molecules. Two vertices are connected by an edge if the matches that they represent are compatible with each other. Being compatible may mean, for instance, that the distances between the atoms within the two molecules are approximately equal, to within some given tolerance. A clique in this graph represents a set of matched pairs of atoms in which all the matches are compatible with each other.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> A special case of this method is the use of the <a href="/facts/Modular_product_of_graphs/8xDk6H1x">modular product of graphs</a> to reduce the problem of finding the <a href="/facts/Maximum_common_induced_subgraph/Yb0pm9Wu">maximum common induced subgraph</a> of two graphs to the problem of finding a maximum clique in their product.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>
In <a href="/facts/Automatic_test_pattern_generation/NGPXXf1o">automatic test pattern generation</a>, finding cliques can help to bound the size of a test set.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> In <a href="/facts/Bioinformatics/D5x2L8ee">bioinformatics</a>, clique-finding algorithms have been used to infer <a href="/facts/Evolutionary_tree/f5vVEpeY">evolutionary trees</a>,<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> <a href="/facts/Protein_structure_prediction/sj6AbLjI">predict protein structures</a>,<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> and find closely interacting clusters of proteins.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> Listing the cliques in a <a href="/facts/Dependency_graph/AVC2CjGX">dependency graph</a> is an important step in the analysis of certain random processes.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> In mathematics, <a href="/facts/Keller%27s_conjecture/KXDD5E5w">Keller's conjecture</a> on face-to-face tiling of <a href="/facts/Hypercube/q2mRPbIz">hypercubes</a> was disproved by Lagarias & Shor (1992), who used a clique-finding algorithm on an associated graph to find a counterexample.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>

<h2 id="definitions">Definitions</h2>
Main article: <a href="/facts/Clique_(graph_theory)/XK9ppLz5">Clique (graph theory)</a>

An <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a> is formed by a <a href="/facts/Finite_set/za1newlP">finite set</a> of <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertices</a> and a set of <a href="/facts/Unordered_pair/lEXzY7LA">unordered pairs</a> of vertices, which are called <a href="/facts/Edge_(graph_theory)/W0MqKkyE">edges</a>. By convention, in algorithm analysis, the number of vertices in the graph is denoted by n and the number of edges is denoted by m. A <a href="/facts/Clique_(graph_theory)/XK9ppLz5">clique</a> in a graph G is a <a href="/facts/Complete_graph/AYD6hUqI">complete</a> <a href="/facts/Glossary_of_graph_theory/W0MqKkyE">subgraph</a> of G. That is, it is a subset K of the vertices such that every two vertices in K are the two endpoints of an edge in G. A <a href="/facts/Maximal_clique/XK9ppLz5">maximal clique</a> is a clique to which no more vertices can be added. For each vertex v that is not part of a maximal clique, there must be another vertex w that is in the clique and non-adjacent to v, preventing v from being added to the clique. A <a href="/facts/Maximum_clique/XK9ppLz5">maximum clique</a> is a clique that includes the largest possible number of vertices. The clique number ω(G) is the number of vertices in a maximum clique of G.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a>
Several closely related clique-finding problems have been studied.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a>

<ul><li>In the maximum clique problem, the input is an undirected graph, and the output is a maximum clique in the graph. If there are multiple maximum cliques, one of them may be chosen arbitrarily.<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a></li>
<li>In the weighted maximum clique problem, the input is an undirected graph with weights on its vertices (or, less frequently, edges) and the output is a clique with maximum total weight. The maximum clique problem is the special case in which all weights are equal.<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a> As well as the problem of optimizing the sum of weights, other more complicated bicriterion optimization problems have also been studied.<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a></li>
<li>In the maximal clique listing problem, the input is an undirected graph, and the output is a list of all its maximal cliques. The maximum clique problem may be solved using as a subroutine an algorithm for the maximal clique listing problem, because the maximum clique must be included among all the maximal cliques.<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a></li>
<li>In the k-clique problem, the input is an undirected graph and a number k. The output is a clique with k vertices, if one exists, or a special value indicating that there is no k-clique otherwise. In some variations of this problem, the output should list all cliques of size k.<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a></li>
<li>In the clique decision problem, the input is an undirected graph and a number k, and the output is a <a href="/facts/Truth_value/SY4e2w8l">Boolean value</a>: true if the graph contains a k-clique, and false otherwise.<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a></li></ul>
The first four of these problems are all important in practical applications. The clique decision problem is not of practical importance; it is formulated in this way in order to apply the theory of <a href="/facts/NP-completeness/NFPv56DU">NP-completeness</a> to clique-finding problems.<a class="footnote-ref" id="fnref:23" href="#fn:23">23</a>
The clique problem and the <a href="/facts/Independent_set_problem/ksu46kdz">independent set problem</a> are complementary: a clique in G is an independent set in the <a href="/facts/Complement_graph/IdHUPFr3">complement graph</a> of G and vice versa.<a class="footnote-ref" id="fnref:24" href="#fn:24">24</a> Therefore, many computational results may be applied equally well to either problem, and some research papers do not clearly distinguish between the two problems. However, the two problems have different properties when applied to restricted families of graphs. For instance, the clique problem may be solved in polynomial time for <a href="/facts/Planar_graph/plREagr9">planar graphs</a><a class="footnote-ref" id="fnref:25" href="#fn:25">25</a> while the independent set problem remains NP-hard on planar graphs.<a class="footnote-ref" id="fnref:26" href="#fn:26">26</a>

<h2 id="algorithms">Algorithms</h2>
<h3>Finding a single maximal clique</h3>
A <a href="/facts/Maximal_element/7FCC9qAW">maximal</a> clique, sometimes called inclusion-maximal, is a clique that is not included in a larger clique. Therefore, every clique is contained in a maximal clique.<a class="footnote-ref" id="fnref:27" href="#fn:27">27</a> Maximal cliques can be very small. A graph may contain a non-maximal clique with many vertices and a separate clique of size 2 which is maximal. While a maximum (i.e., largest) clique is necessarily maximal, the converse does not hold. There are some types of graphs in which every maximal clique is maximum; these are the <a href="/facts/Complement_(graph_theory)/IdHUPFr3">complements</a> of the <a href="/facts/Well-covered_graph/zudc7Bro">well-covered graphs</a>, in which every maximal independent set is maximum.<a class="footnote-ref" id="fnref:28" href="#fn:28">28</a> However, other graphs have maximal cliques that are not maximum.
A single maximal clique can be found by a straightforward <a href="/facts/Greedy_algorithm/alfsekco">greedy algorithm</a>. Starting with an arbitrary clique (for instance, any single vertex or even the empty set), grow the current clique one vertex at a time by looping through the graph's remaining vertices. For each vertex v that this loop examines, add v to the clique if it is adjacent to every vertex that is already in the clique, and discard v otherwise. This algorithm runs in <a href="/facts/Linear_time/77T62gmf">linear time</a>.<a class="footnote-ref" id="fnref:29" href="#fn:29">29</a> Because of the ease of finding maximal cliques, and their potential small size, more attention has been given to the much harder algorithmic problem of finding a maximum or otherwise large clique. However, some research in <a href="/facts/Parallel_algorithm/nUPzEF4C">parallel algorithms</a> has studied the problem of finding a maximal clique. In particular, the problem of finding the <a href="/facts/Lexicographic_ordering/xQANy8Br">lexicographically first</a> maximal clique (the one found by the algorithm above) has been shown to be <a href="/facts/Complete_(complexity)/Ine1b8Qy">complete</a> for <a href="/facts/FP_(complexity)/FSK2uwKz">the class of polynomial-time functions</a>. This result implies that the problem is unlikely to be solvable within the parallel complexity class <a href="/facts/NC_(complexity)/4SY2L2Kg">NC</a>.<a class="footnote-ref" id="fnref:30" href="#fn:30">30</a>

<h3>Cliques of fixed size</h3>
One can test whether a graph G contains a k-vertex clique, and find any such clique that it contains, using a <a href="/facts/Brute-force_search/YU2fzBIt">brute force algorithm</a>. This algorithm examines each subgraph with k vertices and checks to see whether it forms a clique. It takes time O(nk k2), as expressed using <a href="/facts/Big_O_notation/weFFjSWg">big O notation</a>.
This is because there are O(nk) subgraphs to check, each of which has O(k2) edges whose presence in G needs to be checked. Thus, the problem may be solved in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> whenever k is a fixed constant. However, when k does not have a fixed value, but instead may vary as part of the input to the problem, the time is exponential.<a class="footnote-ref" id="fnref:31" href="#fn:31">31</a>
The simplest nontrivial case of the clique-finding problem is finding a triangle in a graph, or equivalently determining whether the graph is <a href="/facts/Triangle-free_graph/8D3LJ44h">triangle-free</a>.
In a graph G with m edges, there may be at most Θ(m3/2) triangles (using <a href="/facts/Big_theta_notation/weFFjSWg">big theta notation</a> to indicate that this bound is tight). The worst case for this formula occurs when G is itself a clique. Therefore, algorithms for listing all triangles must take at least Ω(m3/2) time in the worst case (using <a href="/facts/Big_omega_notation/weFFjSWg">big omega notation</a>), and algorithms are known that match this time bound.<a class="footnote-ref" id="fnref:32" href="#fn:32">32</a> For instance, Chiba & Nishizeki (1985) describe an algorithm that sorts the vertices in order from highest degree to lowest and then iterates through each vertex v in the sorted list, looking for triangles that include v and do not include any previous vertex in the list. To do so the algorithm marks all neighbors of v, searches through all edges incident to a neighbor of v outputting a triangle for every edge that has two marked endpoints, and then removes the marks and deletes v from the graph. As the authors show, the time for this algorithm is proportional to the <a href="/facts/Arboricity/JjfuCv8r">arboricity</a> of the graph (denoted a(G)) multiplied by the number of edges, which is O(m a(G)). Since the arboricity is at most O(m1/2), this algorithm runs in time O(m3/2). More generally, all k-vertex cliques can be listed by a similar algorithm that takes time proportional to the number of edges multiplied by the arboricity to the power (k − 2). For graphs of constant arboricity, such as planar graphs (or in general graphs from any non-trivial <a href="/facts/Minor-closed_graph_family/qn5eI22T">minor-closed graph family</a>), this algorithm takes O(m) time, which is optimal since it is linear in the size of the input.<a class="footnote-ref" id="fnref:33" href="#fn:33">33</a>
If one desires only a single triangle, or an assurance that the graph is triangle-free, faster algorithms are possible. As Itai & Rodeh (1978) observe, the graph contains a triangle if and only if its <a href="/facts/Adjacency_matrix/jYXNhYGs">adjacency matrix</a> and the square of the adjacency matrix contain nonzero entries in the same cell. Therefore, <a href="/facts/Computational_complexity_of_matrix_multiplication/KCn5KUzd">fast matrix multiplication</a> techniques can be applied to find triangles in time O(n2.376). Alon, Yuster & Zwick (1994) used fast matrix multiplication to improve the O(m3/2) algorithm for finding triangles to O(m1.41). These algorithms based on fast matrix multiplication have also been extended to problems of finding k-cliques for larger values of k.<a class="footnote-ref" id="fnref:34" href="#fn:34">34</a>

<h3>Listing all maximal cliques</h3>
By a result of Moon & Moser (1965), every n-vertex graph has at most 3n/3 maximal cliques. They can be listed by the <a href="/facts/Bron%E2%80%93Kerbosch_algorithm/WM0FyQ2U">Bron–Kerbosch algorithm</a>, a recursive <a href="/facts/Backtracking/Jm9vDUk8">backtracking</a> procedure of 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 O(3n/3), matching the number of cliques that might need to be listed.<a class="footnote-ref" id="fnref:35" href="#fn:35">35</a> 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.<a class="footnote-ref" id="fnref:36" href="#fn:36">36</a>
However, when the number of cliques is significantly smaller than its worst case, other algorithms might be preferable. As Tsukiyama et al. (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 <a href="/facts/Output-sensitive_algorithm/5vAv585y">output-sensitive algorithm</a>. Their algorithm is based on the following two observations, relating the maximal cliques of the given graph G to the maximal cliques of a graph G \ v formed by removing an arbitrary vertex v from G:

<ul><li>For every maximal clique K of G \ v, either K continues to form a maximal clique in G, or K ⋃ {v} forms a maximal clique in G. Therefore, G has at least as many maximal cliques as G \ v does.</li>
<li>Each maximal clique in G that does not contain v is a maximal clique in G \ v, and each maximal clique in G that does contain v can be formed from a maximal clique K in G \ v by adding v and removing the non-neighbors of v from K.</li></ul>
Using these observations they can generate all maximal cliques in G by a recursive algorithm that chooses a vertex v arbitrarily and then, for each maximal clique K in G \ v, outputs both K and the clique formed by adding v to K and removing the non-neighbors of v. However, some cliques of G may be generated in this way from more than one parent clique of G \ v, so they eliminate duplicates by outputting a clique in G only when its parent in G \ v is lexicographically maximum among all possible parent cliques. On the basis of this principle, they show that all maximal cliques in G may be generated in time O(mn) per clique, where m is the number of edges in G and n is the number of vertices. Chiba & Nishizeki (1985) improve this to O(ma) per clique, where a is the arboricity of the given graph. Makino & Uno (2004) provide an alternative output-sensitive algorithm based on fast matrix multiplication. Johnson & Yannakakis (1988) show that it is even possible to list all maximal cliques in <a href="/facts/Lexicographic_order/xQANy8Br">lexicographic order</a> with <a href="/facts/Polynomial_delay/FfNjhNM2">polynomial delay</a> 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 <a href="/facts/P_%3D_NP/xoC7Ruda">P = NP</a>.
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 <a href="/facts/Chordal_graph/7hNerUdA">chordal graphs</a>, <a href="/facts/Complete_graph/AYD6hUqI">complete graphs</a>, <a href="/facts/Triangle-free_graph/8D3LJ44h">triangle-free graphs</a>, <a href="/facts/Interval_graph/oLwYI3uT">interval graphs</a>, graphs of bounded <a href="/facts/Boxicity/9aAIvmKe">boxicity</a>, and <a href="/facts/Planar_graph/plREagr9">planar graphs</a>.<a class="footnote-ref" id="fnref:37" href="#fn:37">37</a> In particular, the planar graphs have 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 <a href="/facts/Dense_graph/xFC7b7s9">sparse</a> (having a number of edges at most a constant times the number of vertices) and <a href="/facts/Closure_(mathematics)/Ct6r2fJz">closed</a> under the operation of taking subgraphs.<a class="footnote-ref" id="fnref:38" href="#fn:38">38</a><a class="footnote-ref" id="fnref:39" href="#fn:39">39</a>

<h3>Finding maximum cliques in arbitrary graphs</h3>
It is possible to find the maximum clique, or the clique number, of an arbitrary n-vertex graph in time O(3n/3) = O(1.4422n) by using one of the algorithms described above to list all maximal cliques in the graph and returning the largest one. However, for this variant of the clique problem better worst-case time bounds are possible. The algorithm of Tarjan & Trojanowski (1977) solves this problem in time O(2n/3) = O(1.2599n). It is a recursive backtracking scheme similar to that of the <a href="/facts/Bron%E2%80%93Kerbosch_algorithm/WM0FyQ2U">Bron–Kerbosch algorithm</a>, but is able to eliminate some recursive calls when it can be shown that the cliques found within the call will be suboptimal. Jian (1986) improved the time to O(20.304n) = O(1.2346n), and Robson (1986) improved it to O(20.276n) = O(1.2108n) time, at the expense of greater space usage. Robson's algorithm combines a similar backtracking scheme (with a more complicated case analysis) and a <a href="/facts/Dynamic_programming/CLcabtmk">dynamic programming</a> technique in which the optimal solution is precomputed for all small connected subgraphs of the <a href="/facts/Complement_graph/IdHUPFr3">complement graph</a>. These partial solutions are used to shortcut the backtracking recursion. The fastest algorithm known today is a refined version of this method by Robson (2001) which runs in time O(20.249n) = O(1.1888n).<a class="footnote-ref" id="fnref:40" href="#fn:40">40</a>
There has also been extensive research on <a href="/facts/Heuristic_algorithm/PM2qkoa2">heuristic algorithms</a> for solving maximum clique problems without worst-case runtime guarantees, based on methods including <a href="/facts/Branch_and_bound/mhALtav7">branch and bound</a>,<a class="footnote-ref" id="fnref:41" href="#fn:41">41</a> <a href="/facts/Local_search_(optimization)/G1D2aHBz">local search</a>,<a class="footnote-ref" id="fnref:42" href="#fn:42">42</a> <a href="/facts/Greedy_algorithm/alfsekco">greedy algorithms</a>,<a class="footnote-ref" id="fnref:43" href="#fn:43">43</a> and <a href="/facts/Constraint_programming/rgkCK5bD">constraint programming</a>.<a class="footnote-ref" id="fnref:44" href="#fn:44">44</a> Non-standard computing methodologies that have been suggested for finding cliques include <a href="/facts/DNA_computing/NfNV4obg">DNA computing</a><a class="footnote-ref" id="fnref:45" href="#fn:45">45</a> and <a href="/facts/Adiabatic_quantum_computation/USqCIzRf">adiabatic quantum computation</a>.<a class="footnote-ref" id="fnref:46" href="#fn:46">46</a> The maximum clique problem was the subject of an implementation challenge sponsored by <a href="/facts/DIMACS/gnWKwG0u">DIMACS</a> in 1992–1993,<a class="footnote-ref" id="fnref:47" href="#fn:47">47</a> and a collection of graphs used as benchmarks for the challenge, which is publicly available.<a class="footnote-ref" id="fnref:48" href="#fn:48">48</a>

<h3>Special classes of graphs</h3>

<a href="/facts/Planar_graph/plREagr9">Planar graphs</a>, and other families of sparse graphs, have been discussed above: they have linearly many maximal cliques, of bounded size, that can be listed in linear time.<a class="footnote-ref" id="fnref:49" href="#fn:49">49</a> In particular, for planar graphs, any clique can have at most four vertices, by <a href="/facts/Kuratowski%27s_theorem/Enph2grQ">Kuratowski's theorem</a>.<a class="footnote-ref" id="fnref:50" href="#fn:50">50</a>
<a href="/facts/Perfect_graph/wcPdhjG9">Perfect graphs</a> are defined by the properties that their clique number equals their <a href="/facts/Chromatic_number/J6HoBfP0">chromatic number</a>, and that this equality holds also in each of their <a href="/facts/Induced_subgraph/G3EUC0MQ">induced subgraphs</a>. For perfect graphs, it is possible to find a maximum clique in polynomial time, using an algorithm based on <a href="/facts/Semidefinite_programming/pFN25EKE">semidefinite programming</a>.<a class="footnote-ref" id="fnref:51" href="#fn:51">51</a>
However, this method is complex and non-combinatorial, and specialized clique-finding algorithms have been developed for many subclasses of perfect graphs.<a class="footnote-ref" id="fnref:52" href="#fn:52">52</a> In the <a href="/facts/Complement_graph/IdHUPFr3">complement graphs</a> of <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite graphs</a>, <a href="/facts/K%C5%91nig%27s_theorem_(graph_theory)/WKcLCp5b">Kőnig's theorem</a> allows the maximum clique problem to be solved using techniques for <a href="/facts/Matching_(graph_theory)/s0pUJ7hd">matching</a>. In another class of perfect graphs, the <a href="/facts/Permutation_graph/b3rjc9NI">permutation graphs</a>, a maximum clique is a <a href="/facts/Longest_increasing_subsequence/vodfwHwH">longest decreasing subsequence</a> of the permutation defining the graph and can be found using known algorithms for the longest decreasing subsequence problem. Conversely, every instance of the longest decreasing subsequence problem can be described equivalently as a problem of finding a maximum clique in a permutation graph.<a class="footnote-ref" id="fnref:53" href="#fn:53">53</a> Even, Pnueli & Lempel (1972) provide an alternative quadratic-time algorithm for maximum cliques in <a href="/facts/Comparability_graph/dLht35EJ">comparability graphs</a>, a broader class of perfect graphs that includes the permutation graphs as a special case.<a class="footnote-ref" id="fnref:54" href="#fn:54">54</a> In <a href="/facts/Chordal_graph/7hNerUdA">chordal graphs</a>, the maximal cliques can be found by listing the vertices in an elimination ordering, and checking the clique <a href="/facts/Neighborhood_(graph_theory)/E6V1hk6b">neighborhoods</a> of each vertex in this ordering.<a class="footnote-ref" id="fnref:55" href="#fn:55">55</a>
In some cases, these algorithms can be extended to other, non-perfect, classes of graphs as well. For instance, in a <a href="/facts/Circle_graph/mI27LMXp">circle graph</a>, the neighborhood of each vertex is a permutation graph, so a maximum clique in a circle graph can be found by applying the permutation graph algorithm to each neighborhood.<a class="footnote-ref" id="fnref:56" href="#fn:56">56</a> Similarly, in a <a href="/facts/Unit_disk_graph/oIhoT3Pr">unit disk graph</a> (with a known geometric representation), there is a polynomial time algorithm for maximum cliques based on applying the algorithm for complements of bipartite graphs to shared neighborhoods of pairs of vertices.<a class="footnote-ref" id="fnref:57" href="#fn:57">57</a>

The algorithmic problem of finding a maximum clique in a <a href="/facts/Random_graph/gfQhq1Sz">random graph</a> drawn from the <a href="/facts/Erd%C5%91s%E2%80%93R%C3%A9nyi_model/F6BQ8gIj">Erdős–Rényi model</a> (in which each edge appears with probability 1/2, independently from the other edges) was suggested by Karp (1976). Because the maximum clique in a random graph has logarithmic size with high probability, it
can be found by a brute force search in expected time 2O(log2n). This is a <a href="/facts/Quasi-polynomial_time/77T62gmf">quasi-polynomial time</a> bound.<a class="footnote-ref" id="fnref:58" href="#fn:58">58</a> Although the clique number of such graphs is usually very close to 2 log2n, simple <a href="/facts/Greedy_algorithm/alfsekco">greedy algorithms</a> as well as more sophisticated randomized approximation techniques only find cliques with size log2n, half as big. The number of maximal cliques in such graphs is with high probability exponential in log2n, which prevents methods that list all maximal cliques from running in polynomial time.<a class="footnote-ref" id="fnref:59" href="#fn:59">59</a> Because of the difficulty of this problem, several authors have investigated the <a href="/facts/Planted_clique/nnfhLupw">planted clique</a> problem, the clique problem on random graphs that have been augmented by adding large cliques.<a class="footnote-ref" id="fnref:60" href="#fn:60">60</a> While <a href="/facts/Spectral_graph_theory/tBttgGTh">spectral methods</a><a class="footnote-ref" id="fnref:61" href="#fn:61">61</a> and <a href="/facts/Semidefinite_programming/pFN25EKE">semidefinite programming</a><a class="footnote-ref" id="fnref:62" href="#fn:62">62</a> can detect hidden cliques of size Ω(√n), no polynomial-time algorithms are currently known to detect those of size o(√n) (expressed using <a href="/facts/Big_O_notation/weFFjSWg">little-o notation</a>).<a class="footnote-ref" id="fnref:63" href="#fn:63">63</a>

<h3>Approximation algorithms</h3>
Several authors have considered <a href="/facts/Approximation_algorithm/BWlf7M32">approximation algorithms</a> that attempt to find a clique or independent set that, although not maximum, has size as close to the maximum as can be found in polynomial time. Although much of this work has focused on independent sets in sparse graphs, a case that does not make sense for the complementary clique problem, there has also been work on approximation algorithms that do not use such sparsity assumptions.<a class="footnote-ref" id="fnref:64" href="#fn:64">64</a>
Feige (2004) describes a polynomial time algorithm that finds a clique of size Ω((log n/log log n)2) in any graph that has clique number Ω(n/logkn) for any constant k. By using this algorithm when the clique number of a given input graph is between n/log n and n/log3n, switching to a different algorithm of Boppana & Halldórsson (1992) for graphs with higher clique numbers, and choosing a two-vertex clique if both algorithms fail to find anything, <a href="/facts/Uriel_Feige/2qyp3Hcf">Feige</a> provides an approximation algorithm that finds a clique with a number of vertices within a factor of O(n(log log n)2/log3n) of the maximum. Although the <a href="/facts/Approximation_ratio/BWlf7M32">approximation ratio</a> of this algorithm is weak, it is the best known to date.<a class="footnote-ref" id="fnref:65" href="#fn:65">65</a> The results on <a href="/facts/Hardness_of_approximation/YNKqhcej">hardness of approximation</a> described below suggest that there can be no approximation algorithm with an approximation ratio significantly less than linear.

<h2 id="lower-bounds">Lower bounds</h2>
<h3>NP-completeness</h3>

The clique decision problem is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>. It was one of <a href="/facts/Karp%27s_21_NP-complete_problems/dqu5bBh0">Richard Karp's original 21 problems</a> shown NP-complete in his 1972 paper "Reducibility Among Combinatorial Problems".<a class="footnote-ref" id="fnref:66" href="#fn:66">66</a> This problem was also mentioned in <a href="/facts/Stephen_Cook/GdE35Sm1">Stephen Cook</a>'s paper introducing the theory of NP-complete problems.<a class="footnote-ref" id="fnref:67" href="#fn:67">67</a> 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 <a href="/facts/Many-one_reduction/YUKNlYPh">many-one reduction</a> from the <a href="/facts/Boolean_satisfiability_problem/wBVRjWoy">Boolean satisfiability problem</a>. It describes how to translate Boolean formulas in <a href="/facts/Conjunctive_normal_form/B3sY1lTW">conjunctive normal form</a> (CNF) into equivalent instances of the maximum clique problem.<a class="footnote-ref" id="fnref:68" href="#fn:68">68</a> Satisfiability, in turn, was proved NP-complete in the <a href="/facts/Cook%E2%80%93Levin_theorem/6WN3aUyL">Cook–Levin theorem</a>. From a given CNF formula, Karp forms a graph that has a vertex for every pair (v,c), where v is a variable or its negation and c is a clause in the formula that contains 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 (v,c) to (u,d) whenever c ≠ d and u and v are not each other's negations. If k denotes the number of clauses in the CNF formula, then the k-vertex cliques in this graph represent consistent ways of assigning <a href="/facts/Truth_values/SY4e2w8l">truth values</a> to some of its variables in order to satisfy the formula. Therefore, the formula is satisfiable if and only if a k-vertex clique exists.<a class="footnote-ref" id="fnref:69" href="#fn:69">69</a>
Some NP-complete problems (such as the <a href="/facts/Travelling_salesman_problem/2WEKVLnV">travelling salesman problem</a> in <a href="/facts/Planar_graph/plREagr9">planar graphs</a>) may be solved in time that is exponential in a sublinear function of the input size parameter n, significantly faster than a brute-force search.<a class="footnote-ref" id="fnref:70" href="#fn:70">70</a> 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.<a class="footnote-ref" id="fnref:71" href="#fn:71">71</a>

<h3>Circuit complexity</h3>

The computational difficulty of the clique problem has led it to be used to prove several lower bounds in <a href="/facts/Circuit_complexity/6EzA9Tty">circuit complexity</a>. The existence of a clique of a given size is a <a href="/facts/Hereditary_property/J64xYUGG">monotone graph property</a>, meaning that, if a clique exists in a given graph, it will exist in any <a href="/facts/Glossary_of_graph_theory_terms/W0MqKkyE">supergraph</a>. Because this property is monotone, there must exist a monotone circuit, using only <a href="/facts/And_gate/tVKQD0w1">and gates</a> and <a href="/facts/Or_gate/ox2lHgIM">or gates</a>, 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.<a class="footnote-ref" id="fnref:72" href="#fn:72">72</a> Even if a small number of <a href="/facts/NOT_gate/pGk3qGTI">NOT gates</a> are allowed, the complexity remains superpolynomial.<a class="footnote-ref" id="fnref:73" href="#fn:73">73</a> Additionally, the depth of a monotone circuit for the clique problem using gates of bounded <a href="/facts/Fan-in/VfEexbKM">fan-in</a> must be at least a polynomial in the clique size.<a class="footnote-ref" id="fnref:74" href="#fn:74">74</a>

<h3>Decision tree complexity</h3>

The (deterministic) <a href="/facts/Decision_tree_complexity/FalJqMSd">decision tree complexity</a> of determining a <a href="/facts/Graph_property/bjuIvgb1">graph property</a> is the number of questions of the form "Is there an edge between vertex u and vertex 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 <a href="/facts/Decision_tree_model/FalJqMSd">decision tree</a> for the problem. There are n(n − 1)/2 possible questions to be asked. Therefore, any graph property can be determined with at most n(n − 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.<a class="footnote-ref" id="fnref:75" href="#fn:75">75</a>
Because the property of containing a clique is monotone, it is covered by the <a href="/facts/Aanderaa%E2%80%93Karp%E2%80%93Rosenberg_conjecture/IQVneV63">Aanderaa–Karp–Rosenberg conjecture</a>, which states that the deterministic decision tree complexity of determining any non-trivial monotone graph property is exactly n(n − 1)/2. For arbitrary monotone graph properties, this conjecture remains unproven. However, for deterministic decision trees, and for any k in the range 2 ≤ k ≤ n, the property of containing a k-clique was shown to have decision tree complexity exactly n(n − 1)/2 by Bollobás (1976). Deterministic decision trees also require exponential size to detect cliques, or large polynomial size to detect cliques of bounded size.<a class="footnote-ref" id="fnref:76" href="#fn:76">76</a>
The Aanderaa–Karp–Rosenberg conjecture also states that the randomized decision tree complexity of non-trivial monotone functions is Θ(n2). The conjecture again remains unproven, but has been resolved for the property of containing a k clique for 2 ≤ k ≤ n. This property is known to have randomized decision tree complexity Θ(n2).<a class="footnote-ref" id="fnref:77" href="#fn:77">77</a> For quantum decision trees, the best known lower bound is Ω(n), but no matching algorithm is known for the case of k ≥ 3.<a class="footnote-ref" id="fnref:78" href="#fn:78">78</a>

<h3>Fixed-parameter intractability</h3>
<a href="/facts/Parameterized_complexity/RoyaJGgJ">Parameterized complexity</a> is the <a href="/facts/Computational_complexity_theory/etHuVF3U">complexity-theoretic</a> study of problems that are naturally equipped with a small integer parameter k and for which the problem becomes more difficult as k increases, such as finding 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 n, and a function f, such that the algorithm runs in time f(k) nO(1). That is, it is fixed-parameter tractable if it can be solved in polynomial time for any fixed value of k and moreover if the exponent of the polynomial does not depend on k.<a class="footnote-ref" id="fnref:79" href="#fn:79">79</a>
For finding k-vertex cliques, the brute force search algorithm has running time O(nkk2). Because the exponent of n depends on k, this algorithm is not fixed-parameter tractable.
Although it can be improved by fast <a href="/facts/Matrix_multiplication/lYDB6Ro2">matrix multiplication</a>, the running time still has an exponent that is linear in k. Thus, although the running time of known algorithms for the clique problem is polynomial for any fixed k, these algorithms do not suffice for fixed-parameter tractability. 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, <a href="/facts/W(1)/RoyaJGgJ">W[1]</a>. 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 <a href="/facts/Cook%E2%80%93Levin_theorem/6WN3aUyL">Cook–Levin theorem</a> for parameterized complexity.<a class="footnote-ref" id="fnref:80" href="#fn:80">80</a>
Chen et al. (2006) showed that finding k-vertex cliques cannot be done in time no(k) unless the <a href="/facts/Exponential_time_hypothesis/DpxBBNVK">exponential time hypothesis</a> fails. Again, this provides evidence that no fixed-parameter tractable algorithm is possible.<a class="footnote-ref" id="fnref:81" href="#fn:81">81</a>
Although the problems of listing maximal cliques or finding maximum cliques are unlikely to be fixed-parameter tractable with the parameter 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 <a href="/facts/Degeneracy_(graph_theory)/IaYkus22">degeneracy</a> of the input graph.<a class="footnote-ref" id="fnref:82" href="#fn:82">82</a>

<h3>Hardness of approximation</h3>

Weak results hinting that the clique problem might be hard to approximate have been known for a long time. Garey & Johnson (1978) observed that, because the clique number takes on small integer values and is NP-hard to compute, it cannot have a <a href="/facts/Polynomial-time_approximation_scheme/52Chjx9y">fully polynomial-time approximation scheme</a>, unless P = 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 <a href="/facts/Probabilistically_checkable_proof/dbgntVpK">probabilistically checkable proofs</a>. They used these connections to prove <a href="/facts/Hardness_of_approximation/YNKqhcej">hardness of approximation</a> results for the maximum clique problem.<a class="footnote-ref" id="fnref:83" href="#fn:83">83</a>
After many improvements to these results it is now known that, for every <a href="/facts/Real_number/R02gw5Pb">real number</a> ε > 0, there can be no polynomial time algorithm that approximates the maximum clique to within a factor better than O(n1 − ε), unless <a href="/facts/P_versus_NP_problem/xoC7Ruda">P = NP</a>.<a class="footnote-ref" id="fnref:84" href="#fn:84">84</a>
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.<a class="footnote-ref" id="fnref:85" href="#fn:85">85</a>
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 <a href="/facts/Partial_word/dNLfDnuo">partial word</a> with a 0 or 1 at each examined position and a <a href="/facts/Wildcard_character/LErwSxvh">wildcard character</a> 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 = NP.<a class="footnote-ref" id="fnref:86" href="#fn:86">86</a>

<h2 id="notes">Notes</h2>

<h3>Surveys and textbooks</h3>

<ul><li><a href="/facts/Sanjeev_Arora/W3C8BLQI">Arora, Sanjeev</a>; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-521-42426-4.</li>
<li>Blair, Jean R. S.; Peyton, Barry (1993), "An introduction to chordal graphs and clique trees", <a href="https://digital.library.unt.edu/ark:/67531/metadc1319152/">Graph theory and sparse matrix computation</a>, IMA Vol. Math. Appl., vol. 56, Springer, New York, pp. 1–29, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-1-4613-8369-7_1">10.1007/978-1-4613-8369-7_1</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-4613-8371-0, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1320296">1320296</a>.</li>
<li>Bomze, I. M.; Budinich, M.; Pardalos, P. M.; Pelillo, M. (1999), "The maximum clique problem", Handbook of Combinatorial Optimization, vol. 4, Kluwer Academic Publishers, pp. 1–74, <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.4074">10.1.1.48.4074</a>.</li>
<li><a href="/facts/Thomas_H._Cormen/qJ2Ys15T">Cormen, Thomas H.</a>; <a href="/facts/Charles_E._Leiserson/6Uf19apB">Leiserson, Charles E.</a>; <a href="/facts/Ron_Rivest/nQsIcAKa">Rivest, Ronald L.</a>; <a href="/facts/Clifford_Stein/5ajkVbCm">Stein, Clifford</a> (2001), "34.5.1 The clique problem", <a href="/facts/Introduction_to_Algorithms/o9n7KDsg">Introduction to Algorithms</a> (2nd ed.), MIT Press and McGraw-Hill, pp. 1003–1006, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-262-03293-7.</li>
<li>Downey, R. G.; <a href="/facts/Michael_Fellows/Mmlrxg5L">Fellows, M. R.</a> (1999), Parameterized complexity, <a href="/facts/Springer-Verlag/nAesf6nT">Springer-Verlag</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-387-94883-X.</li>
<li><a href="/facts/Martin_Charles_Golumbic/jjoIMseL">Golumbic, M. C.</a> (1980), Algorithmic Graph Theory and Perfect Graphs, Computer Science and Applied Mathematics, <a href="/facts/Academic_Press/qxoKjzFy">Academic Press</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-444-51530-5.</li>
<li><a href="/facts/Martin_Gr%C3%B6tschel/9I4LlIhv">Grötschel, M.</a>; <a href="/facts/L%C3%A1szl%C3%B3_Lov%C3%A1sz/X0VB38Ee">Lovász, L.</a>; <a href="/facts/Alexander_Schrijver/eJHJNRGz">Schrijver, A.</a> (1988), "9.4 Coloring Perfect Graphs", Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2, <a href="/facts/Springer-Verlag/nAesf6nT">Springer-Verlag</a>, pp. 296–298, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-387-13624-X.</li>
<li>Gutin, G. (2004), "5.3 Independent sets and cliques", in Gross, J. L.; Yellen, J. (eds.), Handbook of graph theory, Discrete Mathematics & Its Applications, CRC Press, pp. 389–402, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-58488-090-5.</li>
<li>Muegge, Ingo; Rarey, Matthias (2001), "Small molecule docking and scoring", Reviews in Computational Chemistry, 17: 1–60, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1002%2F0471224413.ch1">10.1002/0471224413.ch1</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9780471398455.</li>
<li>National Research Council Committee on Mathematical Challenges from Computational Chemistry (1995), <a href="https://digital.library.unt.edu/ark:/67531/metadc709300/">Mathematical Challenges from Theoretical/Computational Chemistry</a>, National Academies Press, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.17226%2F4886">10.17226/4886</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-309-05097-5.</li>
<li>Pelillo, Marcello (2009), "Heuristics for maximum clique and independent set", Encyclopedia of Optimization, Springer, pp. 1508–1520, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-0-387-74759-0_264">10.1007/978-0-387-74759-0_264</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-387-74758-3.</li>
<li><a href="/facts/Michael_D._Plummer/IHIVG4vt">Plummer, Michael D.</a> (1993), <a href="https://web.archive.org/web/20120527164352/http://handle.dtic.mil/100.2/ADA247861">"Well-covered graphs: a survey"</a>, Quaestiones Mathematicae, 16 (3): 253–287, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1080%2F16073606.1993.9631737">10.1080/16073606.1993.9631737</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1254158">1254158</a>, archived from <a href="http://handle.dtic.mil/100.2/ADA247861">the original</a> on May 27, 2012.</li>
<li><a href="/facts/Michael_Sipser/h5Wg22bh">Sipser, M.</a> (1996), <a href="/facts/Introduction_to_the_Theory_of_Computation/CXXk8vfj">Introduction to the Theory of Computation</a>, <a href="/facts/The_Thomson_Corporation/EDNXn9VX">International Thompson Publishing</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-534-94728-X.</li>
<li><a href="/facts/Steven_Skiena/bkDu94TQ">Skiena, Steven S.</a> (2009), The Algorithm Design Manual (2nd ed.), Springer, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-84800-070-4.</li>
<li>Valiente, Gabriel (2002), "Chapter 6: Clique, Independent Set, and Vertex Cover", Algorithms on Trees and Graphs, Springer, pp. 299–350, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-662-04921-1_6">10.1007/978-3-662-04921-1_6</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:118777692">118777692</a>.</li>
<li><a href="/facts/Stanley_Wasserman/HdEXvgsc">Wasserman, Stanley</a>; Faust, Katherine (1994), <a href="https://books.google.com/books?id=CAm2DpIqRUIC&pg=PA276">Social Network Analysis: Methods and Applications</a>, Structural Analysis in the Social Sciences, vol. 8, Cambridge University Press, p. 276, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-521-38707-1.</li></ul>

<h3>Research articles</h3>

<ul><li>Abello, J.; Pardalos, P. M.; <a href="/facts/Mauricio_Resende/RBP1VI8a">Resende, M. G. C.</a> (1999), <a href="https://web.archive.org/web/20170116182554/http://www.mgvis.com/Papers/MassiveDataSets/Cliques.pdf">"On maximum clique problems in very large graphs"</a> (PDF), in Abello, J.; <a href="/facts/Jeffrey_Vitter/zteuWVYh">Vitter, J.</a> (eds.), External Memory Algorithms, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, vol. 50, <a href="/facts/American_Mathematical_Society/fr5gotCt">American Mathematical Society</a>, pp. 119–130, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-8218-1184-3, archived from <a href="http://www.mgvis.com/Papers/MassiveDataSets/Cliques.pdf">the original</a> (PDF) on 2017-01-16, retrieved 2017-01-13.</li>
<li><a href="/facts/Noga_Alon/tuqq2GUl">Alon, N.</a>; Boppana, R. (1987), "The monotone circuit complexity of boolean functions", <a href="/facts/Combinatorica/AxdqUqrp">Combinatorica</a>, 7 (1): 1–22, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF02579196">10.1007/BF02579196</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:17397273">17397273</a>.</li>
<li><a href="/facts/Noga_Alon/tuqq2GUl">Alon, N.</a>; Krivelevich, M.; Sudakov, B. (1998), "Finding a large hidden clique in a random graph", Random Structures & Algorithms, 13 (3–4): 457–466, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1002%2F%28SICI%291098-2418%28199810%2F12%2913%3A3%2F4%3C457%3A%3AAID-RSA14%3E3.0.CO%3B2-W">10.1002/(SICI)1098-2418(199810/12)13:3/4<457::AID-RSA14>3.0.CO;2-W</a>.</li>
<li><a href="/facts/Noga_Alon/tuqq2GUl">Alon, N.</a>; Yuster, R.; <a href="/facts/Uri_Zwick/q9cnA3EU">Zwick, U.</a> (1994), "Finding and counting given length cycles", Proceedings of the 2nd European Symposium on Algorithms, Utrecht, The Netherlands, pp. 354–364.</li>
<li>Amano, Kazuyuki; Maruoka, Akira (2005), "A superpolynomial lower bound for a circuit computing the clique function with at most (1/6)log log N negation gates", <a href="/facts/SIAM_Journal_on_Computing/udF33CP4">SIAM Journal on Computing</a>, 35 (1): 201–216, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2FS0097539701396959">10.1137/S0097539701396959</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2178806">2178806</a>.</li>
<li><a href="/facts/Sanjeev_Arora/W3C8BLQI">Arora, Sanjeev</a>; <a href="/facts/Carsten_Lund/pb0y20Jb">Lund, Carsten</a>; <a href="/facts/Rajeev_Motwani/v0K0IYQm">Motwani, Rajeev</a>; <a href="/facts/Madhu_Sudan/6XbwMvWN">Sudan, Madhu</a>; <a href="/facts/Mario_Szegedy/PIv82GRK">Szegedy, Mario</a> (1998), "Proof verification and the hardness of approximation problems", <a href="/facts/Journal_of_the_ACM/qkIF9LLS">Journal of the ACM</a>, 45 (3): 501–555, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F278298.278306">10.1145/278298.278306</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:8561542">8561542</a>, <a href="/facts/Electronic_Colloquium_on_Computational_Complexity/6Tl8NPAM">ECCC</a> <a href="https://eccc.weizmann.ac.il/report/1998/008/">TR98-008</a>. Originally presented at the 1992 <a href="/facts/Symposium_on_Foundations_of_Computer_Science/t0BvR59t">Symposium on Foundations of Computer Science</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2FSFCS.1992.267823">10.1109/SFCS.1992.267823</a>.</li>
<li><a href="/facts/Sanjeev_Arora/W3C8BLQI">Arora, S.</a>; <a href="/facts/Shmuel_Safra/TjgYodym">Safra, S.</a> (1998), "Probabilistic checking of proofs: A new characterization of NP", <a href="/facts/Journal_of_the_ACM/qkIF9LLS">Journal of the ACM</a>, 45 (1): 70–122, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F273865.273901">10.1145/273865.273901</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:751563">751563</a>. Originally presented at the 1992 <a href="/facts/Symposium_on_Foundations_of_Computer_Science/t0BvR59t">Symposium on Foundations of Computer Science</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2FSFCS.1992.267824">10.1109/SFCS.1992.267824</a>.</li>
<li>Balas, E.; Yu, C. S. (1986), "Finding a maximum clique in an arbitrary graph", <a href="/facts/SIAM_Journal_on_Computing/udF33CP4">SIAM Journal on Computing</a>, 15 (4): 1054–1068, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F0215075">10.1137/0215075</a>.</li>
<li>Barrow, H.; <a href="/facts/Rod_Burstall/BhNTxat5">Burstall, R.</a> (1976), "Subgraph isomorphism, matching relational structures and maximal cliques", Information Processing Letters, 4 (4): 83–84, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0020-0190%2876%2990049-1">10.1016/0020-0190(76)90049-1</a>.</li>
<li>Battiti, R.; Protasi, M. (2001), "Reactive local search for the maximum clique problem", <a href="/facts/Algorithmica/EqSt27Q2">Algorithmica</a>, 29 (4): 610–637, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs004530010074">10.1007/s004530010074</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:1800512">1800512</a>.</li>
<li><a href="/facts/B%C3%A9la_Bollob%C3%A1s/9T1eot5o">Bollobás, Béla</a> (1976), "Complete subgraphs are elusive", <a href="/facts/Journal_of_Combinatorial_Theory/oYS6G76K">Journal of Combinatorial Theory</a>, Series B, 21 (1): 1–7, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0095-8956%2876%2990021-6">10.1016/0095-8956(76)90021-6</a>, <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0095-8956">0095-8956</a>.</li>
<li>Boppana, R.; Halldórsson, M. M. (1992), "Approximating maximum independent sets by excluding subgraphs", <a href="/facts/BIT_Numerical_Mathematics/EGbtcCIT">BIT Numerical Mathematics</a>, 32 (2): 180–196, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF01994876">10.1007/BF01994876</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:123335474">123335474</a>.</li>
<li>Bron, C.; Kerbosch, J. (1973), "Algorithm 457: finding all cliques of an undirected graph", <a href="/facts/Communications_of_the_ACM/Ix1DvEAk">Communications of the ACM</a>, 16 (9): 575–577, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F362342.362367">10.1145/362342.362367</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:13886709">13886709</a>.</li>
<li>Carraghan, R.; Pardalos, P. M. (1990), "An exact algorithm for the maximum clique problem", Operations Research Letters, 9 (6): 375–382, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0167-6377%2890%2990057-C">10.1016/0167-6377(90)90057-C</a>.</li>
<li>Cazals, F.; Karande, C. (2008), "A note on the problem of reporting maximal cliques", <a href="/facts/Theoretical_Computer_Science_(journal)/Apbc0PDL">Theoretical Computer Science</a>, 407 (1): 564–568, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.tcs.2008.05.010">10.1016/j.tcs.2008.05.010</a>.</li>
<li>Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge (2006), "Strong computational lower bounds via parameterized complexity", <a href="/facts/Journal_of_Computer_and_System_Sciences/cNek9ego">Journal of Computer and System Sciences</a>, 72 (8): 1346–1367, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.jcss.2006.04.007">10.1016/j.jcss.2006.04.007</a></li>
<li>Chiba, N.; <a href="/facts/Takao_Nishizeki/ndXnyBDx">Nishizeki, T.</a> (1985), "Arboricity and subgraph listing algorithms", <a href="/facts/SIAM_Journal_on_Computing/udF33CP4">SIAM Journal on Computing</a>, 14 (1): 210–223, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F0214017">10.1137/0214017</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:207051803">207051803</a>.</li>
<li>Childs, A. M.; Farhi, E.; <a href="/facts/Jeffrey_Goldstone/1k9Vw5fd">Goldstone, J.</a>; Gutmann, S. (2002), "Finding cliques by quantum adiabatic evolution", Quantum Information and Computation, 2 (3): 181–191, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/quant-ph/0012104">quant-ph/0012104</a>, <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/2000quant.ph.12104C">2000quant.ph.12104C</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.26421%2FQIC2.3">10.26421/QIC2.3</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:33643794">33643794</a>.</li>
<li>Childs, A. M.; Eisenberg, J. M. (2005), "Quantum algorithms for subset finding", Quantum Information and Computation, 5 (7): 593–604, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/quant-ph/0311038">quant-ph/0311038</a>, <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/2003quant.ph.11038C">2003quant.ph.11038C</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.26421%2FQIC5.7">10.26421/QIC5.7</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:37556989">37556989</a>.</li>
<li>Clark, Brent N.; <a href="/facts/Charles_Colbourn/t0kIUMF6">Colbourn, Charles J.</a>; <a href="/facts/David_S._Johnson/kGSBxucb">Johnson, David S.</a> (1990), "Unit disk graphs", <a href="/facts/Discrete_Mathematics_(journal)/K4e6z8wQ">Discrete Mathematics</a>, 86 (1–3): 165–177, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0012-365X%2890%2990358-O">10.1016/0012-365X(90)90358-O</a></li>
<li><a href="/facts/Stephen_Cook/GdE35Sm1">Cook, S. A.</a> (1971), <a href="http://4mhz.de/cook.html">"The complexity of theorem-proving procedures"</a>, <a href="/facts/Symposium_on_Theory_of_Computing/xsemn7kG">Proc. 3rd ACM Symposium on Theory of Computing</a>, pp. 151–158, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F800157.805047">10.1145/800157.805047</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:7573663">7573663</a>.</li>
<li><a href="/facts/Stephen_Cook/GdE35Sm1">Cook, Stephen A.</a> (1985), "A taxonomy of problems with fast parallel algorithms", <a href="/facts/Information_and_Control/4gdF7pR6">Information and Control</a>, 64 (1–3): 2–22, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2FS0019-9958%2885%2980041-3">10.1016/S0019-9958(85)80041-3</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0837088">0837088</a>.</li>
<li>Day, William H. E.; Sankoff, David (1986), "Computational complexity of inferring phylogenies by compatibility", <a href="/facts/Systematic_Zoology/1DuuMurx">Systematic Zoology</a>, 35 (2): 224–229, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F2413432">10.2307/2413432</a>, <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2413432">2413432</a>.</li>
<li>Downey, R. G.; <a href="/facts/Michael_Fellows/Mmlrxg5L">Fellows, M. R.</a> (1995), "Fixed-parameter tractability and completeness. II. On completeness for W[1]", <a href="/facts/Theoretical_Computer_Science_(journal)/Apbc0PDL">Theoretical Computer Science</a>, 141 (1–2): 109–131, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0304-3975%2894%2900097-3">10.1016/0304-3975(94)00097-3</a>.</li>
<li>Eisenbrand, F.; Grandoni, F. (2004), "On the complexity of fixed parameter clique and dominating set", <a href="/facts/Theoretical_Computer_Science_(journal)/Apbc0PDL">Theoretical Computer Science</a>, 326 (1–3): 57–67, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.tcs.2004.05.009">10.1016/j.tcs.2004.05.009</a>.</li>
<li><a href="/facts/David_Eppstein/hIjTU6nC">Eppstein, David</a>; Löffler, Maarten; Strash, Darren (2013), "Listing all maximal cliques in large sparse real-world graphs in near-optimal time", Journal of Experimental Algorithmics, 18 (3): 3.1, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1103.0318">1103.0318</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F2543629">10.1145/2543629</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:47515491">47515491</a>.</li>
<li><a href="/facts/Paul_Erd%C5%91s/63LoUTe1">Erdős, Paul</a>; <a href="/facts/George_Szekeres/SYAhPzEF">Szekeres, George</a> (1935), <a href="http://www.renyi.hu/~p_erdos/1935-01.pdf">"A combinatorial problem in geometry"</a> (PDF), <a href="/facts/Compositio_Mathematica/Igc7zupB">Compositio Mathematica</a>, 2: 463–470.</li>
<li><a href="/facts/Shimon_Even/urvDI0vA">Even, S.</a>; <a href="/facts/Amir_Pnueli/qJ7mMEXm">Pnueli, A.</a>; <a href="/facts/Abraham_Lempel/689EaYp3">Lempel, A.</a> (1972), "Permutation graphs and transitive graphs", <a href="/facts/Journal_of_the_ACM/qkIF9LLS">Journal of the ACM</a>, 19 (3): 400–410, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F321707.321710">10.1145/321707.321710</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:9501737">9501737</a>.</li>
<li>Fahle, T. (2002), "Simple and fast: Improving a branch-and-bound algorithm for maximum clique", <a href="/facts/European_Symposium_on_Algorithms/X8l7xQpr">Proc. 10th European Symposium on Algorithms</a>, Lecture Notes in Computer Science, vol. 2461, Springer-Verlag, pp. 47–86, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F3-540-45749-6_44">10.1007/3-540-45749-6_44</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-44180-9.</li>
<li><a href="/facts/Uriel_Feige/2qyp3Hcf">Feige, U.</a> (2004), "Approximating maximum clique by removing subgraphs", <a href="/facts/SIAM_Journal_on_Discrete_Mathematics/7BG23qL5">SIAM Journal on Discrete Mathematics</a>, 18 (2): 219–225, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2FS089548010240415X">10.1137/S089548010240415X</a>.</li>
<li><a href="/facts/Uriel_Feige/2qyp3Hcf">Feige, U.</a>; <a href="/facts/Shafi_Goldwasser/aTJJq4mB">Goldwasser, S.</a>; <a href="/facts/L%C3%A1szl%C3%B3_Lov%C3%A1sz/X0VB38Ee">Lovász, L.</a>; <a href="/facts/Shmuel_Safra/TjgYodym">Safra, S</a>; <a href="/facts/Mario_Szegedy/PIv82GRK">Szegedy, M.</a> (1991), "Approximating clique is almost NP-complete", <a href="/facts/Symposium_on_Foundations_of_Computer_Science/t0BvR59t">[1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science</a>, pp. 2–12, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2FSFCS.1991.185341">10.1109/SFCS.1991.185341</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-8186-2445-0, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:46605913">46605913</a>.</li>
<li><a href="/facts/Uriel_Feige/2qyp3Hcf">Feige, U.</a>; Krauthgamer, R. (2000), "Finding and certifying a large hidden clique in a semirandom graph", Random Structures and Algorithms, 16 (2): 195–208, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1002%2F%28SICI%291098-2418%28200003%2916%3A2%3C195%3A%3AAID-RSA5%3E3.0.CO%3B2-A">10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A</a>.</li>
<li>Frank, Ove; Strauss, David (1986), "Markov graphs", <a href="/facts/Journal_of_the_American_Statistical_Association/H513IjxL">Journal of the American Statistical Association</a>, 81 (395): 832–842, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F2289017">10.2307/2289017</a>, <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2289017">2289017</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0860518">0860518</a>.</li>
<li><a href="/facts/Michael_R._Garey/xuSLYs90">Garey, M. R.</a>; <a href="/facts/David_S._Johnson/kGSBxucb">Johnson, D. S.</a> (1978), ""Strong" NP-completeness results: motivation, examples and implications", <a href="/facts/Journal_of_the_ACM/qkIF9LLS">Journal of the ACM</a>, 25 (3): 499–508, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F322077.322090">10.1145/322077.322090</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:18371269">18371269</a>.</li>
<li><a href="/facts/Michael_R._Garey/xuSLYs90">Garey, M. R.</a>; <a href="/facts/David_S._Johnson/kGSBxucb">Johnson, D. S.</a>; <a href="/facts/Larry_Stockmeyer/9lx48AKu">Stockmeyer, L.</a> (1976), "Some simplified NP-complete graph problems", <a href="/facts/Theoretical_Computer_Science_(journal)/Apbc0PDL">Theoretical Computer Science</a>, 1 (3): 237–267, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0304-3975%2876%2990059-1">10.1016/0304-3975(76)90059-1</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0411240">0411240</a>.</li>
<li>Gavril, F. (1973), "Algorithms for a maximum clique and a maximum independent set of a circle graph", Networks, 3 (3): 261–273, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1002%2Fnet.3230030305">10.1002/net.3230030305</a>.</li>
<li>Goldmann, M.; <a href="/facts/Johan_H%C3%A5stad/Rg1L6VdD">Håstad, J.</a> (1992), <a href="http://www.csc.kth.se/%7Ejohanh/monotoneclique.pdf">"A simple lower bound for monotone clique using a communication game"</a> (PDF), <a href="/facts/Information_Processing_Letters/e2u7fEKe">Information Processing Letters</a>, 41 (4): 221–226, <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.185.3065">10.1.1.185.3065</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0020-0190%2892%2990184-W">10.1016/0020-0190(92)90184-W</a>.</li>
<li>Gröger, Hans Dietmar (1992), <a href="https://web.archive.org/web/20150924034620/http://www.inf.u-szeged.hu/actacybernetica/edb/vol10n3/pdf/Groger_1992_ActaCybernetica.pdf">"On the randomized complexity of monotone graph properties"</a> (PDF), Acta Cybernetica, 10 (3): 119–127, archived from <a href="http://www.inf.u-szeged.hu/actacybernetica/edb/vol10n3/pdf/Groger_1992_ActaCybernetica.pdf">the original</a> (PDF) on 2015-09-24, retrieved 2009-10-02</li>
<li>Grosso, A.; Locatelli, M.; Della Croce, F. (2004), "Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem", Journal of Heuristics, 10 (2): 135–152, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1023%2FB%3AHEUR.0000026264.51747.7f">10.1023/B:HEUR.0000026264.51747.7f</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:40764225">40764225</a>.</li>
<li>Halldórsson, M. M. (2000), "Approximations of Weighted Independent Set and Hereditary Subset Problems", <a href="/facts/Journal_of_Graph_Algorithms_and_Applications/7oUrnKzR">Journal of Graph Algorithms and Applications</a>, 4 (1): 1–16, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.7155%2Fjgaa.00020">10.7155/jgaa.00020</a>.</li>
<li>Hamzaoglu, I.; Patel, J. H. (1998), "Test set compaction algorithms for combinational circuits", Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design, pp. 283–289, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F288548.288615">10.1145/288548.288615</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 1-58113-008-2, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:12258606">12258606</a>.</li>
<li><a href="/facts/Frank_Harary/3J2P7l4w">Harary, F.</a>; Ross, I. C. (1957), "A procedure for clique detection using the group matrix", Sociometry, 20 (3), American Sociological Association: 205–215, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F2785673">10.2307/2785673</a>, <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2785673">2785673</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0110590">0110590</a>.</li>
<li><a href="/facts/Johan_H%C3%A5stad/Rg1L6VdD">Håstad, J.</a> (1999), "Clique is hard to approximate within n1 − ε", <a href="/facts/Acta_Mathematica/11kbuhDT">Acta Mathematica</a>, 182 (1): 105–142, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF02392825">10.1007/BF02392825</a>.</li>
<li><a href="/facts/Russell_Impagliazzo/GJ6W46dq">Impagliazzo, R.</a>; Paturi, R.; Zane, F. (2001), "Which problems have strongly exponential complexity?", <a href="/facts/Journal_of_Computer_and_System_Sciences/cNek9ego">Journal of Computer and System Sciences</a>, 63 (4): 512–530, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1006%2Fjcss.2001.1774">10.1006/jcss.2001.1774</a>.</li>
<li>Itai, A.; Rodeh, M. (1978), "Finding a minimum circuit in a graph", <a href="/facts/SIAM_Journal_on_Computing/udF33CP4">SIAM Journal on Computing</a>, 7 (4): 413–423, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F0207033">10.1137/0207033</a>.</li>
<li>Jerrum, M. (1992), "Large cliques elude the Metropolis process", Random Structures and Algorithms, 3 (4): 347–359, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1002%2Frsa.3240030402">10.1002/rsa.3240030402</a>.</li>
<li>Jian, T (1986), "An O(20.304n) algorithm for solving maximum independent set problem", <a href="/facts/IEEE_Transactions_on_Computers/jjc4KLle">IEEE Transactions on Computers</a>, 35 (9), IEEE Computer Society: 847–851, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2FTC.1986.1676847">10.1109/TC.1986.1676847</a>, <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/0018-9340">0018-9340</a>.</li>
<li><a href="/facts/David_S._Johnson/kGSBxucb">Johnson, D. S.</a>; <a href="/facts/Michael_Trick/To62895A">Trick, M. A.</a>, eds. (1996), <a href="http://dimacs.rutgers.edu/Volumes/Vol26.html">Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11–13, 1993</a>, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26, <a href="/facts/American_Mathematical_Society/fr5gotCt">American Mathematical Society</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-8218-6609-5.</li>
<li><a href="/facts/David_S._Johnson/kGSBxucb">Johnson, D. S.</a>; <a href="/facts/Mihalis_Yannakakis/sEHPDT9v">Yannakakis, M.</a> (1988), "On generating all maximal independent sets", <a href="/facts/Information_Processing_Letters/e2u7fEKe">Information Processing Letters</a>, 27 (3): 119–123, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0020-0190%2888%2990065-8">10.1016/0020-0190(88)90065-8</a>.</li>
<li><a href="/facts/Richard_M._Karp/XtYCL0nA">Karp, Richard M.</a> (1972), "Reducibility among combinatorial problems", in Miller, R. E.; Thatcher, J. W. (eds.), <a href="https://web.archive.org/web/20110629023717/http://www.cs.berkeley.edu/~luca/cs172/karp.pdf">Complexity of Computer Computations</a> (PDF), New York: <a href="/facts/Plenum_Publishing_Corporation/nAesf6nT">Plenum</a>, pp. 85–103, archived from <a href="http://www.cs.berkeley.edu/~luca/cs172/karp.pdf">the original</a> (PDF) on 2011-06-29, retrieved 2009-12-17.</li>
<li><a href="/facts/Richard_M._Karp/XtYCL0nA">Karp, Richard M.</a> (1976), "Probabilistic analysis of some combinatorial search problems", in Traub, J. F. (ed.), Algorithms and Complexity: New Directions and Recent Results, New York: <a href="/facts/Academic_Press/qxoKjzFy">Academic Press</a>, pp. 1–19.</li>
<li>Katayama, K.; Hamamoto, A.; Narihisa, H. (2005), "An effective local search for the maximum clique problem", <a href="/facts/Information_Processing_Letters/e2u7fEKe">Information Processing Letters</a>, 95 (5): 503–511, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.ipl.2005.05.010">10.1016/j.ipl.2005.05.010</a>.</li>
<li>Khot, S. (2001), "Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring", <a href="/facts/Symposium_on_Foundations_of_Computer_Science/t0BvR59t">Proceedings 42nd IEEE Symposium on Foundations of Computer Science</a>, pp. 600–609, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2FSFCS.2001.959936">10.1109/SFCS.2001.959936</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-7695-1116-3, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:11987483">11987483</a>.</li>
<li>Kloks, T.; Kratsch, D.; Müller, H. (2000), "Finding and counting small induced subgraphs efficiently", <a href="/facts/Information_Processing_Letters/e2u7fEKe">Information Processing Letters</a>, 74 (3–4): 115–121, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2FS0020-0190%2800%2900047-8">10.1016/S0020-0190(00)00047-8</a>.</li>
<li>Konc, J.; Janežič, D. (2007), <a href="http://insilab.org/articles/match2007.pdf">"An improved branch and bound algorithm for the maximum clique problem"</a> (PDF), MATCH Communications in Mathematical and in Computer Chemistry, 58 (3): 569–590. <a href="http://insilab.org/maxclique">Source code</a></li>
<li>Kuhl, F. S.; Crippen, G. M.; Friesen, D. K. (1983), "A combinatorial algorithm for calculating ligand binding", Journal of Computational Chemistry, 5 (1): 24–34, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1002%2Fjcc.540050105">10.1002/jcc.540050105</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:122923018">122923018</a>.</li>
<li><a href="/facts/Jeffrey_Lagarias/HVvI3c3E">Lagarias, Jeffrey C.</a>; <a href="/facts/Peter_Shor/YIztGkMY">Shor, Peter W.</a> (1992), "Keller's cube-tiling conjecture is false in high dimensions", <a href="/facts/Bulletin_of_the_American_Mathematical_Society/8ER5KY5z">Bulletin of the American Mathematical Society</a>, New Series, 27 (2): 279–283, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/math/9210222">math/9210222</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1090%2FS0273-0979-1992-00318-X">10.1090/S0273-0979-1992-00318-X</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1155280">1155280</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:6390600">6390600</a>.</li>
<li><a href="/facts/Richard_J._Lipton/aMHKxTMH">Lipton, R. J.</a>; <a href="/facts/Robert_Tarjan/kn1pMCN0">Tarjan, R. E.</a> (1980), "Applications of a planar separator theorem", <a href="/facts/SIAM_Journal_on_Computing/udF33CP4">SIAM Journal on Computing</a>, 9 (3): 615–627, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F0209046">10.1137/0209046</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:12961628">12961628</a>.</li>
<li>Liu, Yu; Lu, Jiaheng; Yang, Hua; Xiao, Xiaokui; Wei, Zhewei (2015), "Towards maximum independent sets on massive graphs", <a href="http://www.vldb.org/pvldb/vol8/p2122-lu.pdf">Proceedings of the 41st International Conference on Very Large Data Bases (VLDB 2015)</a> (PDF), Proceedings of the VLDB Endowment, vol. 8, pp. 2122–2133, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.14778%2F2831360.2831366">10.14778/2831360.2831366</a>, <a href="/facts/Hdl_(identifier)/rdebSxmC">hdl</a>:<a href="https://hdl.handle.net/10138%2F157292">10138/157292</a>.</li>
<li><a href="/facts/R._Duncan_Luce/QSJFYkIM">Luce, R. Duncan</a>; Perry, Albert D. (1949), "A method of matrix analysis of group structure", Psychometrika, 14 (2): 95–116, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF02289146">10.1007/BF02289146</a>, <a href="/facts/Hdl_(identifier)/rdebSxmC">hdl</a>:<a href="https://hdl.handle.net/10.1007%2FBF02289146">10.1007/BF02289146</a>, <a href="/facts/PMID_(identifier)/JlHAvMHt">PMID</a> <a href="https://pubmed.ncbi.nlm.nih.gov/18152948">18152948</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:16186758">16186758</a>.</li>
<li>Mackey, John (2002), "A cube tiling of dimension eight with no facesharing", <a href="/facts/Discrete_and_Computational_Geometry/wVPxzUWo">Discrete and Computational Geometry</a>, 28 (2): 275–279, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs00454-002-2801-9">10.1007/s00454-002-2801-9</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1920144">1920144</a>.</li>
<li>Magniez, Frédéric; Santha, Miklos; <a href="/facts/Mario_Szegedy/PIv82GRK">Szegedy, Mario</a> (2007), "Quantum algorithms for the triangle problem", <a href="/facts/SIAM_Journal_on_Computing/udF33CP4">SIAM Journal on Computing</a>, 37 (2): 413–424, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/quant-ph/0310134">quant-ph/0310134</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F050643684">10.1137/050643684</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:594494">594494</a>.</li>
<li>Makino, K.; Uno, T. (2004), "New algorithms for enumerating all maximal cliques", <a href="http://research.nii.ac.jp/~uno/papers/04swat.pdf">Algorithm Theory: SWAT 2004</a> (PDF), Lecture Notes in Computer Science, vol. 3111, <a href="/facts/Springer-Verlag/nAesf6nT">Springer-Verlag</a>, pp. 260–272, <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.705">10.1.1.138.705</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-540-27810-8_23">10.1007/978-3-540-27810-8_23</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-22339-9.</li>
<li>Meka, Raghu; Potechin, Aaron; <a href="/facts/Avi_Wigderson/CVHaUAdI">Wigderson, Avi</a> (2015), "Sum-of-squares lower bounds for planted clique", Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC '15), New York, NY, USA: ACM, pp. 87–96, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1503.06447">1503.06447</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F2746539.2746600">10.1145/2746539.2746600</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-4503-3536-2, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:2754095">2754095</a>.</li>
<li>Moon, J. W.; <a href="/facts/Leo_Moser/f2y27VS3">Moser, L.</a> (1965), "On cliques in graphs", <a href="/facts/Israel_Journal_of_Mathematics/mSGtfzpS">Israel Journal of Mathematics</a>, 3: 23–28, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF02760024">10.1007/BF02760024</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0182577">0182577</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:9855414">9855414</a>.</li>
<li><a href="/facts/Jaroslav_Ne%C5%A1et%C5%99il/99pR0wFP">Nešetřil, J.</a>; Poljak, S. (1985), "On the complexity of the subgraph problem", Commentationes Mathematicae Universitatis Carolinae, 26 (2): 415–419.</li>
<li>Östergård, P. R. J. (2002), "A fast algorithm for the maximum clique problem", <a href="/facts/Discrete_Applied_Mathematics/0xgV889h">Discrete Applied Mathematics</a>, 120 (1–3): 197–207, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2FS0166-218X%2801%2900290-6">10.1016/S0166-218X(01)00290-6</a>.</li>
<li>Ouyang, Q.; Kaplan, P. D.; Liu, S.; Libchaber, A. (1997), "DNA solution of the maximal clique problem", <a href="/facts/Science_(journal)/uTyzjkwD">Science</a>, 278 (5337): 446–449, <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1997Sci...278..446O">1997Sci...278..446O</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1126%2Fscience.278.5337.446">10.1126/science.278.5337.446</a>, <a href="/facts/PMID_(identifier)/JlHAvMHt">PMID</a> <a href="https://pubmed.ncbi.nlm.nih.gov/9334300">9334300</a>.</li>
<li><a href="/facts/Christos_Papadimitriou/rXflR4or">Papadimitriou, Christos H.</a>; <a href="/facts/Mihalis_Yannakakis/sEHPDT9v">Yannakakis, Mihalis</a> (1981), "The clique problem for planar graphs", <a href="/facts/Information_Processing_Letters/e2u7fEKe">Information Processing Letters</a>, 13 (4–5): 131–133, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0020-0190%2881%2990041-7">10.1016/0020-0190(81)90041-7</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0651460">0651460</a>.</li>
<li>Pardalos, P. M.; Rogers, G. P. (1992), "A branch and bound algorithm for the maximum clique problem", Computers & Operations Research, 19 (5): 363–375, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0305-0548%2892%2990067-F">10.1016/0305-0548(92)90067-F</a>.</li>
<li><a href="/facts/Alexander_Razborov/EmMX1W4K">Razborov, A. A.</a> (1985), "Lower bounds for the monotone complexity of some Boolean functions", <a href="/facts/Proceedings_of_the_USSR_Academy_of_Sciences/dqes3C9S">Proceedings of the USSR Academy of Sciences</a> (in Russian), 281: 798–801. English translation in Sov. Math. Dokl. 31 (1985): 354–357{{citation}}: CS1 maint: postscript (link).</li>
<li>Régin, J.-C. (2003), "Using constraint programming to solve the maximum clique problem", Proc. 9th Int. Conf. Principles and Practice of Constraint Programming – CP 2003, Lecture Notes in Computer Science, vol. 2833, <a href="/facts/Springer-Verlag/nAesf6nT">Springer-Verlag</a>, pp. 634–648, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-540-45193-8_43">10.1007/978-3-540-45193-8_43</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-20202-8.</li>
<li>Rhodes, Nicholas; Willett, Peter; Calvet, Alain; Dunbar, James B.; Humblet, Christine (2003), "CLIP: similarity searching of 3D databases using clique detection", Journal of Chemical Information and Computer Sciences, 43 (2): 443–448, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1021%2Fci025605o">10.1021/ci025605o</a>, <a href="/facts/PMID_(identifier)/JlHAvMHt">PMID</a> <a href="https://pubmed.ncbi.nlm.nih.gov/12653507">12653507</a>.</li>
<li>Robson, J. M. (1986), "Algorithms for maximum independent sets", Journal of Algorithms, 7 (3): 425–440, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0196-6774%2886%2990032-5">10.1016/0196-6774(86)90032-5</a>.</li>
<li>Robson, J. M. (2001), <a href="http://www.labri.fr/perso/robson/mis/techrep.html">Finding a maximum independent set in time O(2n/4)</a>.</li>
<li>Rosgen, B; Stewart, L (2007), <a href="https://hal.inria.fr/hal-00966509">"Complexity results on graphs with few cliques"</a>, Discrete Mathematics and Theoretical Computer Science, 9 (1): 127–136.</li>
<li>Samudrala, Ram; Moult, John (1998), "A graph-theoretic algorithm for comparative modeling of protein structure", Journal of Molecular Biology, 279 (1): 287–302, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1006%2Fjmbi.1998.1689">10.1006/jmbi.1998.1689</a>, <a href="/facts/PMID_(identifier)/JlHAvMHt">PMID</a> <a href="https://pubmed.ncbi.nlm.nih.gov/9636717">9636717</a>.</li>
<li>Sethuraman, Samyukta; Butenko, Sergiy (2015), "The maximum ratio clique problem", Computational Management Science, 12 (1): 197–218, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs10287-013-0197-z">10.1007/s10287-013-0197-z</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=3296231">3296231</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:46153055">46153055</a>.</li>
<li>Song, Y. (2015), <a href="https://zenodo.org/record/896067">"On the independent set problem in random graphs"</a>, International Journal of Computer Mathematics, 92 (11): 2233–2242, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1080%2F00207160.2014.976210">10.1080/00207160.2014.976210</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:6713201">6713201</a>.</li>
<li>Spirin, Victor; Mirny, Leonid A. (2003), "Protein complexes and functional modules in molecular networks", <a href="/facts/Proceedings_of_the_National_Academy_of_Sciences/w75CThX0">Proceedings of the National Academy of Sciences</a>, 100 (21): 12123–12128, <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/2003PNAS..10012123S">2003PNAS..10012123S</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1073%2Fpnas.2032324100">10.1073/pnas.2032324100</a>, <a href="/facts/PMC_(identifier)/dX1zMt71">PMC</a> <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC218723">218723</a>, <a href="/facts/PMID_(identifier)/JlHAvMHt">PMID</a> <a href="https://pubmed.ncbi.nlm.nih.gov/14517352">14517352</a>.</li>
<li><a href="/facts/Robert_Tarjan/kn1pMCN0">Tarjan, R. E.</a>; Trojanowski, A. E. (1977), <a href="http://i.stanford.edu/pub/cstr/reports/cs/tr/76/550/CS-TR-76-550.pdf">"Finding a maximum independent set"</a> (PDF), <a href="/facts/SIAM_Journal_on_Computing/udF33CP4">SIAM Journal on Computing</a>, 6 (3): 537–546, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F0206038">10.1137/0206038</a>.</li>
<li>Tomita, E.; Kameda, T. (2007), "An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments", Journal of Global Optimization, 37 (1): 95–111, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs10898-006-9039-7">10.1007/s10898-006-9039-7</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:21436014">21436014</a>.</li>
<li>Tomita, E.; Seki, T. (2003), <a href="https://archive.org/details/discretemathemat0000dmtc/page/278">"An efficient branch-and-bound algorithm for finding a maximum clique"</a>, Discrete Mathematics and Theoretical Computer Science, Lecture Notes in Computer Science, vol. 2731, Springer-Verlag, pp. <a href="https://archive.org/details/discretemathemat0000dmtc/page/278">278–289</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F3-540-45066-1_22">10.1007/3-540-45066-1_22</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-40505-4, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:21436014">21436014</a>.</li>
<li>Tomita, E.; Tanaka, A.; Takahashi, H. (2006), "The worst-case time complexity for generating all maximal cliques and computational experiments", <a href="/facts/Theoretical_Computer_Science_(journal)/Apbc0PDL">Theoretical Computer Science</a>, 363 (1): 28–42, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.tcs.2006.06.015">10.1016/j.tcs.2006.06.015</a>.</li>
<li>Tsukiyama, S.; Ide, M.; Ariyoshi, I.; Shirakawa, I. (1977), "A new algorithm for generating all the maximal independent sets", <a href="/facts/SIAM_Journal_on_Computing/udF33CP4">SIAM Journal on Computing</a>, 6 (3): 505–517, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F0206036">10.1137/0206036</a>.</li>
<li>Valiant, L. G. (1983), "Exponential lower bounds for restricted monotone circuits", <a href="/facts/Symposium_on_Theory_of_Computing/xsemn7kG">Proc. 15th ACM Symposium on Theory of Computing</a>, pp. 110–117, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F800061.808739">10.1145/800061.808739</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-89791-099-0, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:6326587">6326587</a>.</li>
<li><a href="/facts/Virginia_Vassilevska_Williams/dd7jUV8W">Vassilevska, V.</a>; <a href="/facts/Ryan_Williams_(computer_scientist)/U0Cmse8x">Williams, R.</a> (2009), "Finding, minimizing, and counting weighted subgraphs", <a href="/facts/Symposium_on_Theory_of_Computing/xsemn7kG">Proc. 41st ACM Symposium on Theory of Computing</a>, pp. 455–464, <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.345">10.1.1.156.345</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F1536414.1536477">10.1145/1536414.1536477</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-60558-506-2, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:224579">224579</a>.</li>
<li>Wegener, I. (1988), "On the complexity of branching programs and decision trees for clique functions", <a href="/facts/Journal_of_the_ACM/qkIF9LLS">Journal of the ACM</a>, 35 (2): 461–472, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F42282.46161">10.1145/42282.46161</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:11967153">11967153</a>.</li>
<li>Yuster, R. (2006), "Finding and counting cliques and independent sets in r-uniform hypergraphs", <a href="/facts/Information_Processing_Letters/e2u7fEKe">Information Processing Letters</a>, 99 (4): 130–134, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.ipl.2006.04.005">10.1016/j.ipl.2006.04.005</a>.</li>
<li>Zuckerman, D. (2006), "Linear degree extractors and the inapproximability of max clique and chromatic number", <a href="/facts/Symposium_on_Theory_of_Computing/xsemn7kG">Proc. 38th ACM Symp. Theory of Computing</a>, pp. 681–690, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F1132516.1132612">10.1145/1132516.1132612</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 1-59593-134-1, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:5713815">5713815</a>, <a href="/facts/Electronic_Colloquium_on_Computational_Complexity/6Tl8NPAM">ECCC</a> <a href="https://eccc.weizmann.ac.il/report/2005/100/">TR05-100</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Bomze et al. (1999); Gutin (2004). - Bomze, I. M.; Budinich, M.; Pardalos, P. M.; Pelillo, M. (1999), "The maximum clique problem", Handbook of Combinatorial Optimization, vol. 4, Kluwer Academic Publishers, pp. 1–74, CiteSeerX 10.1.1.48.4074 <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.4074" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.4074</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Wasserman & Faust (1994). - Wasserman, Stanley; Faust, Katherine (1994), Social Network Analysis: Methods and Applications, Structural Analysis in the Social Sciences, vol. 8, Cambridge University Press, p. 276, ISBN 978-0-521-38707-1 <a href="https://books.google.com/books?id=CAm2DpIqRUIC&pg=PA276" target="_blank">https://books.google.com/books?id=CAm2DpIqRUIC&pg=PA276</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Bomze et al. (1999); Gutin (2004). - Bomze, I. M.; Budinich, M.; Pardalos, P. M.; Pelillo, M. (1999), "The maximum clique problem", Handbook of Combinatorial Optimization, vol. 4, Kluwer Academic Publishers, pp. 1–74, CiteSeerX 10.1.1.48.4074 <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.4074" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.4074</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Rhodes et al. (2003). - Rhodes, Nicholas; Willett, Peter; Calvet, Alain; Dunbar, James B.; Humblet, Christine (2003), "CLIP: similarity searching of 3D databases using clique detection", Journal of Chemical Information and Computer Sciences, 43 (2): 443–448, doi:10.1021/ci025605o, PMID 12653507 <a href="https://doi.org/10.1021%2Fci025605o" target="_blank">https://doi.org/10.1021%2Fci025605o</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Kuhl, Crippen & Friesen (1983). - Kuhl, F. S.; Crippen, G. M.; Friesen, D. K. (1983), "A combinatorial algorithm for calculating ligand binding", Journal of Computational Chemistry, 5 (1): 24–34, doi:10.1002/jcc.540050105, S2CID 122923018 <a href="https://doi.org/10.1002%2Fjcc.540050105" target="_blank">https://doi.org/10.1002%2Fjcc.540050105</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">National Research Council Committee on Mathematical Challenges from Computational Chemistry (1995). See in particular pp. 35–36. - National Research Council Committee on Mathematical Challenges from Computational Chemistry (1995), Mathematical Challenges from Theoretical/Computational Chemistry, National Academies Press, doi:10.17226/4886, ISBN 978-0-309-05097-5 <a href="https://digital.library.unt.edu/ark:/67531/metadc709300/" target="_blank">https://digital.library.unt.edu/ark:/67531/metadc709300/</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Muegge & Rarey (2001). See in particular pp. 6–7. - Muegge, Ingo; Rarey, Matthias (2001), "Small molecule docking and scoring", Reviews in Computational Chemistry, 17: 1–60, doi:10.1002/0471224413.ch1, ISBN 9780471398455 <a href="https://doi.org/10.1002%2F0471224413.ch1" target="_blank">https://doi.org/10.1002%2F0471224413.ch1</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Barrow & Burstall (1976). - Barrow, H.; Burstall, R. (1976), "Subgraph isomorphism, matching relational structures and maximal cliques", Information Processing Letters, 4 (4): 83–84, doi:10.1016/0020-0190(76)90049-1 <a href="https://doi.org/10.1016%2F0020-0190%2876%2990049-1" target="_blank">https://doi.org/10.1016%2F0020-0190%2876%2990049-1</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Hamzaoglu & Patel (1998). - Hamzaoglu, I.; Patel, J. H. (1998), "Test set compaction algorithms for combinational circuits", Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design, pp. 283–289, doi:10.1145/288548.288615, ISBN 1-58113-008-2, S2CID 12258606 <a href="https://doi.org/10.1145%2F288548.288615" target="_blank">https://doi.org/10.1145%2F288548.288615</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Day & Sankoff (1986). - Day, William H. E.; Sankoff, David (1986), "Computational complexity of inferring phylogenies by compatibility", Systematic Zoology, 35 (2): 224–229, doi:10.2307/2413432, JSTOR 2413432 <a href="https://doi.org/10.2307%2F2413432" target="_blank">https://doi.org/10.2307%2F2413432</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Samudrala & Moult (1998). - Samudrala, Ram; Moult, John (1998), "A graph-theoretic algorithm for comparative modeling of protein structure", Journal of Molecular Biology, 279 (1): 287–302, doi:10.1006/jmbi.1998.1689, PMID 9636717 <a href="https://doi.org/10.1006%2Fjmbi.1998.1689" target="_blank">https://doi.org/10.1006%2Fjmbi.1998.1689</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Spirin & Mirny (2003). - Spirin, Victor; Mirny, Leonid A. (2003), "Protein complexes and functional modules in molecular networks", Proceedings of the National Academy of Sciences, 100 (21): 12123–12128, Bibcode:2003PNAS..10012123S, doi:10.1073/pnas.2032324100, PMC 218723, PMID 14517352 <a href="https://ui.adsabs.harvard.edu/abs/2003PNAS..10012123S" target="_blank">https://ui.adsabs.harvard.edu/abs/2003PNAS..10012123S</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Frank & Strauss (1986). - Frank, Ove; Strauss, David (1986), "Markov graphs", Journal of the American Statistical Association, 81 (395): 832–842, doi:10.2307/2289017, JSTOR 2289017, MR 0860518 <a href="https://doi.org/10.2307%2F2289017" target="_blank">https://doi.org/10.2307%2F2289017</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">The Keller graph used by Lagarias & Shor (1992) has 1048576 vertices and clique size 1024. They described a synthetic construction for the clique, but also used clique-finding algorithms on smaller graphs to help guide their search. Mackey (2002) simplified the proof by finding a clique of size 256 in a 65536-vertex Keller graph. - Lagarias, Jeffrey C.; Shor, Peter W. (1992), "Keller's cube-tiling conjecture is false in high dimensions", Bulletin of the American Mathematical Society, New Series, 27 (2): 279–283, arXiv:math/9210222, doi:10.1090/S0273-0979-1992-00318-X, MR 1155280, S2CID 6390600 <a href="https://arxiv.org/abs/math/9210222" target="_blank">https://arxiv.org/abs/math/9210222</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Bomze et al. (1999); Gutin (2004). - Bomze, I. M.; Budinich, M.; Pardalos, P. M.; Pelillo, M. (1999), "The maximum clique problem", Handbook of Combinatorial Optimization, vol. 4, Kluwer Academic Publishers, pp. 1–74, CiteSeerX 10.1.1.48.4074 <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.4074" target="_blank">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.4074</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Valiente (2002); Pelillo (2009). - Valiente, Gabriel (2002), "Chapter 6: Clique, Independent Set, and Vertex Cover", Algorithms on Trees and Graphs, Springer, pp. 299–350, doi:10.1007/978-3-662-04921-1_6, S2CID 118777692 <a href="https://doi.org/10.1007%2F978-3-662-04921-1_6" target="_blank">https://doi.org/10.1007%2F978-3-662-04921-1_6</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Valiente (2002); Pelillo (2009). - Valiente, Gabriel (2002), "Chapter 6: Clique, Independent Set, and Vertex Cover", Algorithms on Trees and Graphs, Springer, pp. 299–350, doi:10.1007/978-3-662-04921-1_6, S2CID 118777692 <a href="https://doi.org/10.1007%2F978-3-662-04921-1_6" target="_blank">https://doi.org/10.1007%2F978-3-662-04921-1_6</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Pelillo (2009). - Pelillo, Marcello (2009), "Heuristics for maximum clique and independent set", Encyclopedia of Optimization, Springer, pp. 1508–1520, doi:10.1007/978-0-387-74759-0_264, ISBN 978-0-387-74758-3 <a href="https://doi.org/10.1007%2F978-0-387-74759-0_264" target="_blank">https://doi.org/10.1007%2F978-0-387-74759-0_264</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Sethuraman & Butenko (2015). - Sethuraman, Samyukta; Butenko, Sergiy (2015), "The maximum ratio clique problem", Computational Management Science, 12 (1): 197–218, doi:10.1007/s10287-013-0197-z, MR 3296231, S2CID 46153055 <a href="https://doi.org/10.1007%2Fs10287-013-0197-z" target="_blank">https://doi.org/10.1007%2Fs10287-013-0197-z</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Valiente (2002). - Valiente, Gabriel (2002), "Chapter 6: Clique, Independent Set, and Vertex Cover", Algorithms on Trees and Graphs, Springer, pp. 299–350, doi:10.1007/978-3-662-04921-1_6, S2CID 118777692 <a href="https://doi.org/10.1007%2F978-3-662-04921-1_6" target="_blank">https://doi.org/10.1007%2F978-3-662-04921-1_6</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Chiba & Nishizeki (1985). - Chiba, N.; Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing, 14 (1): 210–223, doi:10.1137/0214017, S2CID 207051803 <a href="https://doi.org/10.1137%2F0214017" target="_blank">https://doi.org/10.1137%2F0214017</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Cormen et al. (2001). - Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "34.5.1 The clique problem", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 1003–1006, ISBN 0-262-03293-7 <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Cormen et al. (2001). - Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "34.5.1 The clique problem", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 1003–1006, ISBN 0-262-03293-7 <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">Cormen et al. (2001), Exercise 34-1, p. 1018. - Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "34.5.1 The clique problem", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 1003–1006, ISBN 0-262-03293-7 <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
<li id="fn:25">Papadimitriou & Yannakakis (1981); Chiba & Nishizeki (1985). - Papadimitriou, Christos H.; Yannakakis, Mihalis (1981), "The clique problem for planar graphs", Information Processing Letters, 13 (4–5): 131–133, doi:10.1016/0020-0190(81)90041-7, MR 0651460 <a href="https://doi.org/10.1016%2F0020-0190%2881%2990041-7" target="_blank">https://doi.org/10.1016%2F0020-0190%2881%2990041-7</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></li>
<li id="fn:26">Garey, Johnson & Stockmeyer (1976). - Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1976), "Some simplified NP-complete graph problems", Theoretical Computer Science, 1 (3): 237–267, doi:10.1016/0304-3975(76)90059-1, MR 0411240 <a href="https://doi.org/10.1016%2F0304-3975%2876%2990059-1" target="_blank">https://doi.org/10.1016%2F0304-3975%2876%2990059-1</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></li>
<li id="fn:27">See, e.g., Frank & Strauss (1986). - Frank, Ove; Strauss, David (1986), "Markov graphs", Journal of the American Statistical Association, 81 (395): 832–842, doi:10.2307/2289017, JSTOR 2289017, MR 0860518 <a href="https://doi.org/10.2307%2F2289017" target="_blank">https://doi.org/10.2307%2F2289017</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></li>
<li id="fn:28">Plummer (1993). - Plummer, Michael D. (1993), "Well-covered graphs: a survey", Quaestiones Mathematicae, 16 (3): 253–287, doi:10.1080/16073606.1993.9631737, MR 1254158, archived from the original on May 27, 2012 <a href="https://web.archive.org/web/20120527164352/http://handle.dtic.mil/100.2/ADA247861" target="_blank">https://web.archive.org/web/20120527164352/http://handle.dtic.mil/100.2/ADA247861</a> <a href="#fnref:28" class="footnote-back-ref">↩</a></li>
<li id="fn:29">Skiena (2009), p. 526. - Skiena, Steven S. (2009), The Algorithm Design Manual (2nd ed.), Springer, ISBN 978-1-84800-070-4 <a href="#fnref:29" class="footnote-back-ref">↩</a></li>
<li id="fn:30">Cook (1985). - Cook, Stephen A. (1985), "A taxonomy of problems with fast parallel algorithms", Information and Control, 64 (1–3): 2–22, doi:10.1016/S0019-9958(85)80041-3, MR 0837088 <a href="https://doi.org/10.1016%2FS0019-9958%2885%2980041-3" target="_blank">https://doi.org/10.1016%2FS0019-9958%2885%2980041-3</a> <a href="#fnref:30" class="footnote-back-ref">↩</a></li>
<li id="fn:31">E.g., see Downey & Fellows (1995). - Downey, R. G.; Fellows, M. R. (1995), "Fixed-parameter tractability and completeness. II. On completeness for W[1]", Theoretical Computer Science, 141 (1–2): 109–131, doi:10.1016/0304-3975(94)00097-3 <a href="https://doi.org/10.1016%2F0304-3975%2894%2900097-3" target="_blank">https://doi.org/10.1016%2F0304-3975%2894%2900097-3</a> <a href="#fnref:31" class="footnote-back-ref">↩</a></li>
<li id="fn:32">Itai & Rodeh (1978) provide an algorithm with O(m3/2) running time that finds a triangle if one exists but does not list all triangles; Chiba & Nishizeki (1985) list all triangles in time O(m3/2). - Itai, A.; Rodeh, M. (1978), "Finding a minimum circuit in a graph", SIAM Journal on Computing, 7 (4): 413–423, doi:10.1137/0207033 <a href="https://doi.org/10.1137%2F0207033" target="_blank">https://doi.org/10.1137%2F0207033</a> <a href="#fnref:32" class="footnote-back-ref">↩</a></li>
<li id="fn:33">Chiba & Nishizeki (1985). - Chiba, N.; Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing, 14 (1): 210–223, doi:10.1137/0214017, S2CID 207051803 <a href="https://doi.org/10.1137%2F0214017" target="_blank">https://doi.org/10.1137%2F0214017</a> <a href="#fnref:33" class="footnote-back-ref">↩</a></li>
<li id="fn:34">Eisenbrand & Grandoni (2004); Kloks, Kratsch & Müller (2000); Nešetřil & Poljak (1985); Vassilevska & Williams (2009); Yuster (2006). - Eisenbrand, F.; Grandoni, F. (2004), "On the complexity of fixed parameter clique and dominating set", Theoretical Computer Science, 326 (1–3): 57–67, doi:10.1016/j.tcs.2004.05.009 <a href="https://doi.org/10.1016%2Fj.tcs.2004.05.009" target="_blank">https://doi.org/10.1016%2Fj.tcs.2004.05.009</a> <a href="#fnref:34" class="footnote-back-ref">↩</a></li>
<li id="fn:35">Tomita, Tanaka & Takahashi (2006). - Tomita, E.; Tanaka, A.; Takahashi, H. (2006), "The worst-case time complexity for generating all maximal cliques and computational experiments", Theoretical Computer Science, 363 (1): 28–42, doi:10.1016/j.tcs.2006.06.015 <a href="https://doi.org/10.1016%2Fj.tcs.2006.06.015" target="_blank">https://doi.org/10.1016%2Fj.tcs.2006.06.015</a> <a href="#fnref:35" class="footnote-back-ref">↩</a></li>
<li id="fn:36">Cazals & Karande (2008); Eppstein, Löffler & Strash (2013). - Cazals, F.; Karande, C. (2008), "A note on the problem of reporting maximal cliques", Theoretical Computer Science, 407 (1): 564–568, doi:10.1016/j.tcs.2008.05.010 <a href="https://doi.org/10.1016%2Fj.tcs.2008.05.010" target="_blank">https://doi.org/10.1016%2Fj.tcs.2008.05.010</a> <a href="#fnref:36" class="footnote-back-ref">↩</a></li>
<li id="fn:37">Rosgen & Stewart (2007). - Rosgen, B; Stewart, L (2007), "Complexity results on graphs with few cliques", Discrete Mathematics and Theoretical Computer Science, 9 (1): 127–136 <a href="https://hal.inria.fr/hal-00966509" target="_blank">https://hal.inria.fr/hal-00966509</a> <a href="#fnref:37" class="footnote-back-ref">↩</a></li>
<li id="fn:38">Chiba & Nishizeki (1985). - Chiba, N.; Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing, 14 (1): 210–223, doi:10.1137/0214017, S2CID 207051803 <a href="https://doi.org/10.1137%2F0214017" target="_blank">https://doi.org/10.1137%2F0214017</a> <a href="#fnref:38" class="footnote-back-ref">↩</a></li>
<li id="fn:39">Eppstein, Löffler & Strash (2013). - Eppstein, David; Löffler, Maarten; Strash, Darren (2013), "Listing all maximal cliques in large sparse real-world graphs in near-optimal time", Journal of Experimental Algorithmics, 18 (3): 3.1, arXiv:1103.0318, doi:10.1145/2543629, S2CID 47515491 <a href="https://arxiv.org/abs/1103.0318" target="_blank">https://arxiv.org/abs/1103.0318</a> <a href="#fnref:39" class="footnote-back-ref">↩</a></li>
<li id="fn:40">Robson (2001). - Robson, J. M. (2001), Finding a maximum independent set in time O(2n/4) <a href="http://www.labri.fr/perso/robson/mis/techrep.html" target="_blank">http://www.labri.fr/perso/robson/mis/techrep.html</a> <a href="#fnref:40" class="footnote-back-ref">↩</a></li>
<li id="fn:41">Balas & Yu (1986); Carraghan & Pardalos (1990); Pardalos & Rogers (1992); Östergård (2002); Fahle (2002); Tomita & Seki (2003); Tomita & Kameda (2007); Konc & Janežič (2007). - Balas, E.; Yu, C. S. (1986), "Finding a maximum clique in an arbitrary graph", SIAM Journal on Computing, 15 (4): 1054–1068, doi:10.1137/0215075 <a href="https://doi.org/10.1137%2F0215075" target="_blank">https://doi.org/10.1137%2F0215075</a> <a href="#fnref:41" class="footnote-back-ref">↩</a></li>
<li id="fn:42">Battiti & Protasi (2001); Katayama, Hamamoto & Narihisa (2005). - Battiti, R.; Protasi, M. (2001), "Reactive local search for the maximum clique problem", Algorithmica, 29 (4): 610–637, doi:10.1007/s004530010074, S2CID 1800512 <a href="https://doi.org/10.1007%2Fs004530010074" target="_blank">https://doi.org/10.1007%2Fs004530010074</a> <a href="#fnref:42" class="footnote-back-ref">↩</a></li>
<li id="fn:43">Abello, Pardalos & Resende (1999); Grosso, Locatelli & Della Croce (2004). - Abello, J.; Pardalos, P. M.; Resende, M. G. C. (1999), "On maximum clique problems in very large graphs" (PDF), in Abello, J.; Vitter, J. (eds.), External Memory Algorithms, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, vol. 50, American Mathematical Society, pp. 119–130, ISBN 0-8218-1184-3, archived from the original (PDF) on 2017-01-16, retrieved 2017-01-13 <a href="https://web.archive.org/web/20170116182554/http://www.mgvis.com/Papers/MassiveDataSets/Cliques.pdf" target="_blank">https://web.archive.org/web/20170116182554/http://www.mgvis.com/Papers/MassiveDataSets/Cliques.pdf</a> <a href="#fnref:43" class="footnote-back-ref">↩</a></li>
<li id="fn:44">Régin (2003). - Régin, J.-C. (2003), "Using constraint programming to solve the maximum clique problem", Proc. 9th Int. Conf. Principles and Practice of Constraint Programming – CP 2003, Lecture Notes in Computer Science, vol. 2833, Springer-Verlag, pp. 634–648, doi:10.1007/978-3-540-45193-8_43, ISBN 978-3-540-20202-8 <a href="https://doi.org/10.1007%2F978-3-540-45193-8_43" target="_blank">https://doi.org/10.1007%2F978-3-540-45193-8_43</a> <a href="#fnref:44" class="footnote-back-ref">↩</a></li>
<li id="fn:45">Ouyang et al. (1997). Although the title refers to maximal cliques, the problem this paper solves is actually the maximum clique problem. - Ouyang, Q.; Kaplan, P. D.; Liu, S.; Libchaber, A. (1997), "DNA solution of the maximal clique problem", Science, 278 (5337): 446–449, Bibcode:1997Sci...278..446O, doi:10.1126/science.278.5337.446, PMID 9334300 <a href="https://ui.adsabs.harvard.edu/abs/1997Sci...278..446O" target="_blank">https://ui.adsabs.harvard.edu/abs/1997Sci...278..446O</a> <a href="#fnref:45" class="footnote-back-ref">↩</a></li>
<li id="fn:46">Childs et al. (2002). - Childs, A. M.; Farhi, E.; Goldstone, J.; Gutmann, S. (2002), "Finding cliques by quantum adiabatic evolution", Quantum Information and Computation, 2 (3): 181–191, arXiv:quant-ph/0012104, Bibcode:2000quant.ph.12104C, doi:10.26421/QIC2.3, S2CID 33643794 <a href="https://arxiv.org/abs/quant-ph/0012104" target="_blank">https://arxiv.org/abs/quant-ph/0012104</a> <a href="#fnref:46" class="footnote-back-ref">↩</a></li>
<li id="fn:47">Johnson & Trick (1996). - Johnson, D. S.; Trick, M. A., eds. (1996), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11–13, 1993, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26, American Mathematical Society, ISBN 0-8218-6609-5 <a href="http://dimacs.rutgers.edu/Volumes/Vol26.html" target="_blank">http://dimacs.rutgers.edu/Volumes/Vol26.html</a> <a href="#fnref:47" class="footnote-back-ref">↩</a></li>
<li id="fn:48">DIMACS challenge graphs for the clique problem Archived 2018-03-30 at the Wayback Machine, accessed 2009-12-17. <a href="http://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/clique/" target="_blank">http://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/clique/</a> <a href="#fnref:48" class="footnote-back-ref">↩</a></li>
<li id="fn:49">Chiba & Nishizeki (1985). - Chiba, N.; Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing, 14 (1): 210–223, doi:10.1137/0214017, S2CID 207051803 <a href="https://doi.org/10.1137%2F0214017" target="_blank">https://doi.org/10.1137%2F0214017</a> <a href="#fnref:49" class="footnote-back-ref">↩</a></li>
<li id="fn:50">Papadimitriou & Yannakakis (1981); Chiba & Nishizeki (1985). - Papadimitriou, Christos H.; Yannakakis, Mihalis (1981), "The clique problem for planar graphs", Information Processing Letters, 13 (4–5): 131–133, doi:10.1016/0020-0190(81)90041-7, MR 0651460 <a href="https://doi.org/10.1016%2F0020-0190%2881%2990041-7" target="_blank">https://doi.org/10.1016%2F0020-0190%2881%2990041-7</a> <a href="#fnref:50" class="footnote-back-ref">↩</a></li>
<li id="fn:51">Grötschel, Lovász & Schrijver (1988). - Grötschel, M.; Lovász, L.; Schrijver, A. (1988), "9.4 Coloring Perfect Graphs", Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2, Springer-Verlag, pp. 296–298, ISBN 0-387-13624-X <a href="#fnref:51" class="footnote-back-ref">↩</a></li>
<li id="fn:52">Golumbic (1980). - Golumbic, M. C. (1980), Algorithmic Graph Theory and Perfect Graphs, Computer Science and Applied Mathematics, Academic Press, ISBN 0-444-51530-5 <a href="#fnref:52" class="footnote-back-ref">↩</a></li>
<li id="fn:53">Golumbic (1980), p. 159. - Golumbic, M. C. (1980), Algorithmic Graph Theory and Perfect Graphs, Computer Science and Applied Mathematics, Academic Press, ISBN 0-444-51530-5 <a href="#fnref:53" class="footnote-back-ref">↩</a></li>
<li id="fn:54">Even, Pnueli & Lempel (1972). - Even, S.; Pnueli, A.; Lempel, A. (1972), "Permutation graphs and transitive graphs", Journal of the ACM, 19 (3): 400–410, doi:10.1145/321707.321710, S2CID 9501737 <a href="https://doi.org/10.1145%2F321707.321710" target="_blank">https://doi.org/10.1145%2F321707.321710</a> <a href="#fnref:54" class="footnote-back-ref">↩</a></li>
<li id="fn:55">Blair & Peyton (1993), Lemma 4.5, p. 19. - Blair, Jean R. S.; Peyton, Barry (1993), "An introduction to chordal graphs and clique trees", Graph theory and sparse matrix computation, IMA Vol. Math. Appl., vol. 56, Springer, New York, pp. 1–29, doi:10.1007/978-1-4613-8369-7_1, ISBN 978-1-4613-8371-0, MR 1320296 <a href="https://digital.library.unt.edu/ark:/67531/metadc1319152/" target="_blank">https://digital.library.unt.edu/ark:/67531/metadc1319152/</a> <a href="#fnref:55" class="footnote-back-ref">↩</a></li>
<li id="fn:56">Gavril (1973); Golumbic (1980), p. 247. - Gavril, F. (1973), "Algorithms for a maximum clique and a maximum independent set of a circle graph", Networks, 3 (3): 261–273, doi:10.1002/net.3230030305 <a href="https://doi.org/10.1002%2Fnet.3230030305" target="_blank">https://doi.org/10.1002%2Fnet.3230030305</a> <a href="#fnref:56" class="footnote-back-ref">↩</a></li>
<li id="fn:57">Clark, Colbourn & Johnson (1990). - Clark, Brent N.; Colbourn, Charles J.; Johnson, David S. (1990), "Unit disk graphs", Discrete Mathematics, 86 (1–3): 165–177, doi:10.1016/0012-365X(90)90358-O <a href="https://doi.org/10.1016%2F0012-365X%2890%2990358-O" target="_blank">https://doi.org/10.1016%2F0012-365X%2890%2990358-O</a> <a href="#fnref:57" class="footnote-back-ref">↩</a></li>
<li id="fn:58">Song (2015). - Song, Y. (2015), "On the independent set problem in random graphs", International Journal of Computer Mathematics, 92 (11): 2233–2242, doi:10.1080/00207160.2014.976210, S2CID 6713201 <a href="https://zenodo.org/record/896067" target="_blank">https://zenodo.org/record/896067</a> <a href="#fnref:58" class="footnote-back-ref">↩</a></li>
<li id="fn:59">Jerrum (1992). - Jerrum, M. (1992), "Large cliques elude the Metropolis process", Random Structures and Algorithms, 3 (4): 347–359, doi:10.1002/rsa.3240030402 <a href="https://doi.org/10.1002%2Frsa.3240030402" target="_blank">https://doi.org/10.1002%2Frsa.3240030402</a> <a href="#fnref:59" class="footnote-back-ref">↩</a></li>
<li id="fn:60">Arora & Barak (2009), Example 18.2, pp. 362–363. - Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press, ISBN 978-0-521-42426-4 <a href="#fnref:60" class="footnote-back-ref">↩</a></li>
<li id="fn:61">Alon, Krivelevich & Sudakov (1998). - Alon, N.; Krivelevich, M.; Sudakov, B. (1998), "Finding a large hidden clique in a random graph", Random Structures & Algorithms, 13 (3–4): 457–466, doi:10.1002/(SICI)1098-2418(199810/12)13:3/4<457::AID-RSA14>3.0.CO;2-W <a href="https://doi.org/10.1002%2F%28SICI%291098-2418%28199810%2F12%2913%3A3%2F4%3C457%3A%3AAID-RSA14%3E3.0.CO%3B2-W" target="_blank">https://doi.org/10.1002%2F%28SICI%291098-2418%28199810%2F12%2913%3A3%2F4%3C457%3A%3AAID-RSA14%3E3.0.CO%3B2-W</a> <a href="#fnref:61" class="footnote-back-ref">↩</a></li>
<li id="fn:62">Feige & Krauthgamer (2000). - Feige, U.; Krauthgamer, R. (2000), "Finding and certifying a large hidden clique in a semirandom graph", Random Structures and Algorithms, 16 (2): 195–208, doi:10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A <a href="https://doi.org/10.1002%2F%28SICI%291098-2418%28200003%2916%3A2%3C195%3A%3AAID-RSA5%3E3.0.CO%3B2-A" target="_blank">https://doi.org/10.1002%2F%28SICI%291098-2418%28200003%2916%3A2%3C195%3A%3AAID-RSA5%3E3.0.CO%3B2-A</a> <a href="#fnref:62" class="footnote-back-ref">↩</a></li>
<li id="fn:63">Meka, Potechin & Wigderson (2015). - Meka, Raghu; Potechin, Aaron; Wigderson, Avi (2015), "Sum-of-squares lower bounds for planted clique", Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC '15), New York, NY, USA: ACM, pp. 87–96, arXiv:1503.06447, doi:10.1145/2746539.2746600, ISBN 978-1-4503-3536-2, S2CID 2754095 <a href="https://arxiv.org/abs/1503.06447" target="_blank">https://arxiv.org/abs/1503.06447</a> <a href="#fnref:63" class="footnote-back-ref">↩</a></li>
<li id="fn:64">Boppana & Halldórsson (1992); Feige (2004); Halldórsson (2000). - Boppana, R.; Halldórsson, M. M. (1992), "Approximating maximum independent sets by excluding subgraphs", BIT Numerical Mathematics, 32 (2): 180–196, doi:10.1007/BF01994876, S2CID 123335474 <a href="https://doi.org/10.1007%2FBF01994876" target="_blank">https://doi.org/10.1007%2FBF01994876</a> <a href="#fnref:64" class="footnote-back-ref">↩</a></li>
<li id="fn:65">Liu et al. (2015): "In terms of the number of vertices in graphs, Feige shows the currently known best approximation ratio". Liu et al. are writing about the maximum independent set but for purposes of approximation there is no difference between the two problems. - Liu, Yu; Lu, Jiaheng; Yang, Hua; Xiao, Xiaokui; Wei, Zhewei (2015), "Towards maximum independent sets on massive graphs", Proceedings of the 41st International Conference on Very Large Data Bases (VLDB 2015) (PDF), Proceedings of the VLDB Endowment, vol. 8, pp. 2122–2133, doi:10.14778/2831360.2831366, hdl:10138/157292 <a href="http://www.vldb.org/pvldb/vol8/p2122-lu.pdf" target="_blank">http://www.vldb.org/pvldb/vol8/p2122-lu.pdf</a> <a href="#fnref:65" class="footnote-back-ref">↩</a></li>
<li id="fn:66">Karp (1972). - Karp, Richard M. (1972), "Reducibility among combinatorial problems", in Miller, R. E.; Thatcher, J. W. (eds.), Complexity of Computer Computations (PDF), New York: Plenum, pp. 85–103, archived from the original (PDF) on 2011-06-29, retrieved 2009-12-17 <a href="https://web.archive.org/web/20110629023717/http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" target="_blank">https://web.archive.org/web/20110629023717/http://www.cs.berkeley.edu/~luca/cs172/karp.pdf</a> <a href="#fnref:66" class="footnote-back-ref">↩</a></li>
<li id="fn:67">Cook (1971). - Cook, S. A. (1971), "The complexity of theorem-proving procedures", Proc. 3rd ACM Symposium on Theory of Computing, pp. 151–158, doi:10.1145/800157.805047, S2CID 7573663 <a href="http://4mhz.de/cook.html" target="_blank">http://4mhz.de/cook.html</a> <a href="#fnref:67" class="footnote-back-ref">↩</a></li>
<li id="fn:68">Cook (1971) gives essentially the same reduction, from 3-SAT instead of Satisfiability, to show that subgraph isomorphism is NP-complete. - Cook, S. A. (1971), "The complexity of theorem-proving procedures", Proc. 3rd ACM Symposium on Theory of Computing, pp. 151–158, doi:10.1145/800157.805047, S2CID 7573663 <a href="http://4mhz.de/cook.html" target="_blank">http://4mhz.de/cook.html</a> <a href="#fnref:68" class="footnote-back-ref">↩</a></li>
<li id="fn:69">Karp (1972). - Karp, Richard M. (1972), "Reducibility among combinatorial problems", in Miller, R. E.; Thatcher, J. W. (eds.), Complexity of Computer Computations (PDF), New York: Plenum, pp. 85–103, archived from the original (PDF) on 2011-06-29, retrieved 2009-12-17 <a href="https://web.archive.org/web/20110629023717/http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" target="_blank">https://web.archive.org/web/20110629023717/http://www.cs.berkeley.edu/~luca/cs172/karp.pdf</a> <a href="#fnref:69" class="footnote-back-ref">↩</a></li>
<li id="fn:70">Lipton & Tarjan (1980). - Lipton, R. J.; Tarjan, R. E. (1980), "Applications of a planar separator theorem", SIAM Journal on Computing, 9 (3): 615–627, doi:10.1137/0209046, S2CID 12961628 <a href="https://doi.org/10.1137%2F0209046" target="_blank">https://doi.org/10.1137%2F0209046</a> <a href="#fnref:70" class="footnote-back-ref">↩</a></li>
<li id="fn:71">Impagliazzo, Paturi & Zane (2001). - Impagliazzo, R.; Paturi, R.; Zane, F. (2001), "Which problems have strongly exponential complexity?", Journal of Computer and System Sciences, 63 (4): 512–530, doi:10.1006/jcss.2001.1774 <a href="https://doi.org/10.1006%2Fjcss.2001.1774" target="_blank">https://doi.org/10.1006%2Fjcss.2001.1774</a> <a href="#fnref:71" class="footnote-back-ref">↩</a></li>
<li id="fn:72">Alon & Boppana (1987). For earlier and weaker bounds on monotone circuits for the clique problem, see Valiant (1983) and Razborov (1985). - Alon, N.; Boppana, R. (1987), "The monotone circuit complexity of boolean functions", Combinatorica, 7 (1): 1–22, doi:10.1007/BF02579196, S2CID 17397273 <a href="https://doi.org/10.1007%2FBF02579196" target="_blank">https://doi.org/10.1007%2FBF02579196</a> <a href="#fnref:72" class="footnote-back-ref">↩</a></li>
<li id="fn:73">Amano & Maruoka (2005). - Amano, Kazuyuki; Maruoka, Akira (2005), "A superpolynomial lower bound for a circuit computing the clique function with at most (1/6)log log N negation gates", SIAM Journal on Computing, 35 (1): 201–216, doi:10.1137/S0097539701396959, MR 2178806 <a href="https://doi.org/10.1137%2FS0097539701396959" target="_blank">https://doi.org/10.1137%2FS0097539701396959</a> <a href="#fnref:73" class="footnote-back-ref">↩</a></li>
<li id="fn:74">Goldmann & Håstad (1992) used communication complexity to prove this result. - Goldmann, M.; Håstad, J. (1992), "A simple lower bound for monotone clique using a communication game" (PDF), Information Processing Letters, 41 (4): 221–226, CiteSeerX 10.1.1.185.3065, doi:10.1016/0020-0190(92)90184-W <a href="http://www.csc.kth.se/%7Ejohanh/monotoneclique.pdf" target="_blank">http://www.csc.kth.se/%7Ejohanh/monotoneclique.pdf</a> <a href="#fnref:74" class="footnote-back-ref">↩</a></li>
<li id="fn:75">See Arora & Barak (2009), Chapter 12, "Decision trees", pp. 259–269. - Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press, ISBN 978-0-521-42426-4 <a href="#fnref:75" class="footnote-back-ref">↩</a></li>
<li id="fn:76">Wegener (1988). - Wegener, I. (1988), "On the complexity of branching programs and decision trees for clique functions", Journal of the ACM, 35 (2): 461–472, doi:10.1145/42282.46161, S2CID 11967153 <a href="https://doi.org/10.1145%2F42282.46161" target="_blank">https://doi.org/10.1145%2F42282.46161</a> <a href="#fnref:76" class="footnote-back-ref">↩</a></li>
<li id="fn:77">For instance, this follows from Gröger (1992). - Gröger, Hans Dietmar (1992), "On the randomized complexity of monotone graph properties" (PDF), Acta Cybernetica, 10 (3): 119–127, archived from the original (PDF) on 2015-09-24, retrieved 2009-10-02 <a href="https://web.archive.org/web/20150924034620/http://www.inf.u-szeged.hu/actacybernetica/edb/vol10n3/pdf/Groger_1992_ActaCybernetica.pdf" target="_blank">https://web.archive.org/web/20150924034620/http://www.inf.u-szeged.hu/actacybernetica/edb/vol10n3/pdf/Groger_1992_ActaCybernetica.pdf</a> <a href="#fnref:77" class="footnote-back-ref">↩</a></li>
<li id="fn:78">Childs & Eisenberg (2005); Magniez, Santha & Szegedy (2007). - Childs, A. M.; Eisenberg, J. M. (2005), "Quantum algorithms for subset finding", Quantum Information and Computation, 5 (7): 593–604, arXiv:quant-ph/0311038, Bibcode:2003quant.ph.11038C, doi:10.26421/QIC5.7, S2CID 37556989 <a href="https://arxiv.org/abs/quant-ph/0311038" target="_blank">https://arxiv.org/abs/quant-ph/0311038</a> <a href="#fnref:78" class="footnote-back-ref">↩</a></li>
<li id="fn:79">Downey & Fellows (1999). Technically, there is usually an additional requirement that f be a computable function. - Downey, R. G.; Fellows, M. R. (1999), Parameterized complexity, Springer-Verlag, ISBN 0-387-94883-X <a href="#fnref:79" class="footnote-back-ref">↩</a></li>
<li id="fn:80">Downey & Fellows (1995). - Downey, R. G.; Fellows, M. R. (1995), "Fixed-parameter tractability and completeness. II. On completeness for W[1]", Theoretical Computer Science, 141 (1–2): 109–131, doi:10.1016/0304-3975(94)00097-3 <a href="https://doi.org/10.1016%2F0304-3975%2894%2900097-3" target="_blank">https://doi.org/10.1016%2F0304-3975%2894%2900097-3</a> <a href="#fnref:80" class="footnote-back-ref">↩</a></li>
<li id="fn:81">Chen et al. (2006). - Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge (2006), "Strong computational lower bounds via parameterized complexity", Journal of Computer and System Sciences, 72 (8): 1346–1367, doi:10.1016/j.jcss.2006.04.007 <a href="https://doi.org/10.1016%2Fj.jcss.2006.04.007" target="_blank">https://doi.org/10.1016%2Fj.jcss.2006.04.007</a> <a href="#fnref:81" class="footnote-back-ref">↩</a></li>
<li id="fn:82">Eppstein, Löffler & Strash (2013). - Eppstein, David; Löffler, Maarten; Strash, Darren (2013), "Listing all maximal cliques in large sparse real-world graphs in near-optimal time", Journal of Experimental Algorithmics, 18 (3): 3.1, arXiv:1103.0318, doi:10.1145/2543629, S2CID 47515491 <a href="https://arxiv.org/abs/1103.0318" target="_blank">https://arxiv.org/abs/1103.0318</a> <a href="#fnref:82" class="footnote-back-ref">↩</a></li>
<li id="fn:83">Feige et al. (1991); Arora & Safra (1998); Arora et al. (1998). - Feige, U.; Goldwasser, S.; Lovász, L.; Safra, S; Szegedy, M. (1991), "Approximating clique is almost NP-complete", [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, pp. 2–12, doi:10.1109/SFCS.1991.185341, ISBN 0-8186-2445-0, S2CID 46605913 <a href="https://doi.org/10.1109%2FSFCS.1991.185341" target="_blank">https://doi.org/10.1109%2FSFCS.1991.185341</a> <a href="#fnref:83" class="footnote-back-ref">↩</a></li>
<li id="fn:84">Håstad (1999) showed inapproximability for this ratio using a stronger complexity theoretic assumption, the inequality of NP and ZPP. Khot (2001) described more precisely the inapproximability ratio, but with an even stronger assumption. Zuckerman (2006) derandomized the construction weakening its assumption to P ≠ NP. - Håstad, J. (1999), "Clique is hard to approximate within n1 − ε", Acta Mathematica, 182 (1): 105–142, doi:10.1007/BF02392825 <a href="https://doi.org/10.1007%2FBF02392825" target="_blank">https://doi.org/10.1007%2FBF02392825</a> <a href="#fnref:84" class="footnote-back-ref">↩</a></li>
<li id="fn:85">This reduction is originally due to Feige et al. (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. - Feige, U.; Goldwasser, S.; Lovász, L.; Safra, S; Szegedy, M. (1991), "Approximating clique is almost NP-complete", [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, pp. 2–12, doi:10.1109/SFCS.1991.185341, ISBN 0-8186-2445-0, S2CID 46605913 <a href="https://doi.org/10.1109%2FSFCS.1991.185341" target="_blank">https://doi.org/10.1109%2FSFCS.1991.185341</a> <a href="#fnref:85" class="footnote-back-ref">↩</a></li>
<li id="fn:86">This reduction is originally due to Feige et al. (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. - Feige, U.; Goldwasser, S.; Lovász, L.; Safra, S; Szegedy, M. (1991), "Approximating clique is almost NP-complete", [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, pp. 2–12, doi:10.1109/SFCS.1991.185341, ISBN 0-8186-2445-0, S2CID 46605913 <a href="https://doi.org/10.1109%2FSFCS.1991.185341" target="_blank">https://doi.org/10.1109%2FSFCS.1991.185341</a> <a href="#fnref:86" class="footnote-back-ref">↩</a></li>
</ol>

Clique problem open-in-new

Clique problem