Incubator escapee wiki

Clique problem

Article Discussion

Template:Short description Template:Good article

File:Brute force Clique algorithm.svg
The brute force algorithm finds a 4-clique in this 7-vertex graph (the complement of the 7-vertex path graph) by systematically checking all C(7,4) = 35 4-vertex subgraphs for completeness.

In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a maximum clique (a clique with the largest possible number of vertices), finding a maximum weight clique in a weighted graph, listing all maximal cliques (cliques that cannot be enlarged), and solving the decision problem of testing whether a graph contains a clique larger than a given size.

The clique problem arises in the following real-world setting. Consider a social network, where the graph's vertices represent people, and the graph's edges represent mutual acquaintance. Then a clique represents a subset of people who all know each other, and algorithms for finding cliques can be used to discover these groups of mutual friends. Along with its applications in social networks, the clique problem also has many applications in bioinformatics, and computational chemistry.

Most versions of the clique problem are hard. The clique decision problem is NP-complete (one of Karp's 21 NP-complete problems). The problem of finding the maximum clique is both fixed-parameter intractable and hard to approximate. And, listing all maximal cliques may require exponential time as there exist graphs with exponentially many maximal cliques. Therefore, much of the theory about the clique problem is devoted to identifying special types of graphs that admit more efficient algorithms, or to establishing the computational difficulty of the general problem in various models of computation.

To find a maximum clique, one can systematically inspect all subsets, but this sort of brute-force search is too time-consuming to be practical for networks comprising more than a few dozen vertices. Although no polynomial time algorithm is known for this problem, more efficient algorithms than the brute-force search are known. For instance, the Bron–Kerbosch algorithm can be used to list all maximal cliques in worst-case optimal time, and it is also possible to list them in polynomial time per clique.

History and applicationsEdit

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 Ramsey theory by Template:Harvtxt. But the term "clique" and the problem of algorithmically listing cliques both come from the social sciences, where complete subgraphs are used to model social cliques, groups of people who all know each other. Template:Harvtxt 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 Template:Harvtxt,<ref name="bbpp">Template:Harvtxt; Template:Harvtxt.</ref> 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.Template:Sfnp

Since the work of Harary and Ross, many others have devised algorithms for various versions of the clique problem.<ref name="bbpp"/> In the 1970s, researchers began studying these algorithms from the point of view of worst-case analysis. See, for instance, Template:Harvtxt, an early work on the worst-case complexity of the maximum clique problem. Also in the 1970s, beginning with the work of Template:Harvtxt and Template:Harvtxt, researchers began using the theory of NP-completeness 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 Template:Harvtxt showed that (assuming P ≠ NP) it is not even possible to approximate the problem accurately and efficiently.

Clique-finding algorithms have been used in chemistry, to find chemicals that match a target structureTemplate:Sfnp and to model molecular docking and the binding sites of chemical reactions.Template:Sfnp They can also be used to find similar structures within different molecules.<ref>Template:Harvtxt. See in particular pp. 35–36.</ref> 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.<ref>Template:Harvtxt. See in particular pp. 6–7.</ref> A special case of this method is the use of the modular product of graphs to reduce the problem of finding the maximum common induced subgraph of two graphs to the problem of finding a maximum clique in their product.Template:Sfnp

In automatic test pattern generation, finding cliques can help to bound the size of a test set.Template:Sfnp In bioinformatics, clique-finding algorithms have been used to infer evolutionary trees,Template:Sfnp predict protein structures,Template:Sfnp and find closely interacting clusters of proteins.Template:Sfnp Listing the cliques in a dependency graph is an important step in the analysis of certain random processes.Template:Sfnp In mathematics, Keller's conjecture on face-to-face tiling of hypercubes was disproved by Template:Harvtxt, who used a clique-finding algorithm on an associated graph to find a counterexample.<ref>The Keller graph used by Template:Harvtxt 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. Template:Harvtxt simplified the proof by finding a clique of size 256 in a 65536-vertex Keller graph.</ref>

DefinitionsEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}}

File:6n-graf-clique.svg
The graph shown has one maximum clique, the triangle {1,2,5}, and four more maximal cliques, the pairs {2,3}, {3,4}, {4,5}, and {4,6}.

An undirected graph is formed by a finite set of vertices and a set of unordered pairs of vertices, which are called edges. By convention, in algorithm analysis, the number of vertices in the graph is denoted by Template:Mvar and the number of edges is denoted by Template:Mvar. A clique in a graph Template:Mvar is a complete subgraph of Template:Mvar. That is, it is a subset Template:Mvar of the vertices such that every two vertices in Template:Mvar are the two endpoints of an edge in Template:Mvar. A maximal clique is a clique to which no more vertices can be added. For each vertex Template:Mvar that is not part of a maximal clique, there must be another vertex Template:Mvar that is in the clique and non-adjacent to Template:Mvar, preventing Template:Mvar from being added to the clique. A maximum clique is a clique that includes the largest possible number of vertices. The clique number Template:Math is the number of vertices in a maximum clique of Template:Mvar.<ref name="bbpp"/>

Several closely related clique-finding problems have been studied.<ref name="v02p09">Template:Harvtxt; Template:Harvtxt.</ref>

  • 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.<ref name="v02p09"/>
  • 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.Template:Sfnp As well as the problem of optimizing the sum of weights, other more complicated bicriterion optimization problems have also been studied.Template:Sfnp
  • 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.Template:Sfnp
  • In the Template:Mvar-clique problem, the input is an undirected graph and a number Template:Mvar. The output is a clique with Template:Mvar vertices, if one exists, or a special value indicating that there is no Template:Mvar-clique otherwise. In some variations of this problem, the output should list all cliques of size Template:Mvar.<ref name="CN85"/>
  • In the clique decision problem, the input is an undirected graph and a number Template:Mvar, and the output is a Boolean value: true if the graph contains a Template:Mvar-clique, and false otherwise.Template:Sfnp

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 NP-completeness to clique-finding problems.Template:Sfnp

The clique problem and the independent set problem are complementary: a clique in Template:Mvar is an independent set in the complement graph of Template:Mvar and vice versa.<ref>Template:Harvtxt, Exercise 34-1, p. 1018.</ref> 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 planar graphs<ref name="planar">Template:Harvtxt; Template:Harvtxt.</ref> while the independent set problem remains NP-hard on planar graphs.Template:Sfnp

AlgorithmsEdit

Finding a single maximal cliqueEdit

A maximal 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.<ref>See, e.g., Template:Harvtxt.</ref> 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 complements of the well-covered graphs, in which every maximal independent set is maximum.Template:Sfnp However, other graphs have maximal cliques that are not maximum.

A single maximal clique can be found by a straightforward greedy algorithm. 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 Template:Mvar that this loop examines, add Template:Mvar to the clique if it is adjacent to every vertex that is already in the clique, and discard Template:Mvar otherwise. This algorithm runs in linear time.<ref>Template:Harvtxt, p. 526.</ref> 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 parallel algorithms has studied the problem of finding a maximal clique. In particular, the problem of finding the lexicographically first maximal clique (the one found by the algorithm above) has been shown to be complete for the class of polynomial-time functions. This result implies that the problem is unlikely to be solvable within the parallel complexity class NC.Template:Sfnp

Cliques of fixed sizeEdit

One can test whether a graph Template:Mvar contains a Template:Mvar-vertex clique, and find any such clique that it contains, using a brute force algorithm. This algorithm examines each subgraph with Template:Mvar vertices and checks to see whether it forms a clique. It takes time Template:Math, as expressed using big O notation. This is because there are Template:Math subgraphs to check, each of which has Template:Math edges whose presence in Template:Mvar needs to be checked. Thus, the problem may be solved in polynomial time whenever Template:Mvar is a fixed constant. However, when Template:Mvar does not have a fixed value, but instead may vary as part of the input to the problem, the time is exponential.<ref>E.g., see Template:Harvtxt.</ref>

The simplest nontrivial case of the clique-finding problem is finding a triangle in a graph, or equivalently determining whether the graph is triangle-free. In a graph Template:Mvar with Template:Mvar edges, there may be at most Template:Math triangles (using big theta notation to indicate that this bound is tight). The worst case for this formula occurs when Template:Mvar is itself a clique. Therefore, algorithms for listing all triangles must take at least Template:Math time in the worst case (using big omega notation), and algorithms are known that match this time bound.<ref>Template:Harvtxt provide an algorithm with Template:Math running time that finds a triangle if one exists but does not list all triangles; Template:Harvtxt list all triangles in time Template:Math.</ref> For instance, Template:Harvtxt describe an algorithm that sorts the vertices in order from highest degree to lowest and then iterates through each vertex Template:Mvar in the sorted list, looking for triangles that include Template:Mvar and do not include any previous vertex in the list. To do so the algorithm marks all neighbors of Template:Mvar, searches through all edges incident to a neighbor of Template:Mvar outputting a triangle for every edge that has two marked endpoints, and then removes the marks and deletes Template:Mvar from the graph. As the authors show, the time for this algorithm is proportional to the arboricity of the graph (denoted Template:Math) multiplied by the number of edges, which is Template:Math. Since the arboricity is at most Template:Math, this algorithm runs in time Template:Math. More generally, all Template:Mvar-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 Template:Math. For graphs of constant arboricity, such as planar graphs (or in general graphs from any non-trivial minor-closed graph family), this algorithm takes Template:Math time, which is optimal since it is linear in the size of the input.<ref name="CN85">Template:Harvtxt.</ref>

If one desires only a single triangle, or an assurance that the graph is triangle-free, faster algorithms are possible. As Template:Harvtxt observe, the graph contains a triangle if and only if its adjacency matrix and the square of the adjacency matrix contain nonzero entries in the same cell. Therefore, fast matrix multiplication techniques can be applied to find triangles in time Template:Math. Template:Harvtxt used fast matrix multiplication to improve the Template:Math algorithm for finding triangles to Template:Math. These algorithms based on fast matrix multiplication have also been extended to problems of finding Template:Mvar-cliques for larger values of Template:Mvar.<ref>Template:Harvtxt; Template:Harvtxt; Template:Harvtxt; Template:Harvtxt; Template:Harvtxt.</ref>

Listing all maximal cliquesEdit

By a result of Template:Harvtxt, every Template:Mvar-vertex graph has at most Template:Math maximal cliques. They can be listed by the Bron–Kerbosch algorithm, a recursive backtracking procedure of Template:Harvtxt. 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 Template:Math, matching the number of cliques that might need to be listed.Template:Sfnp Therefore, this provides a worst-case-optimal solution to the problem of listing all maximal cliques. Further, the Bron–Kerbosch algorithm has been widely reported as being faster in practice than its alternatives.<ref>Template:Harvtxt; Template:Harvtxt.</ref>

However, when the number of cliques is significantly smaller than its worst case, other algorithms might be preferable. As Template:Harvtxt showed, it is also possible to list all maximal cliques in a graph in an amount of time that is polynomial per generated clique. An algorithm such as theirs in which the running time depends on the output size is known as an output-sensitive algorithm. Their algorithm is based on the following two observations, relating the maximal cliques of the given graph Template:Mvar to the maximal cliques of a graph Template:Math formed by removing an arbitrary vertex Template:Mvar from Template:Mvar:

Using these observations they can generate all maximal cliques in Template:Mvar by a recursive algorithm that chooses a vertex Template:Mvar arbitrarily and then, for each maximal clique Template:Mvar in Template:Math, outputs both Template:Mvar and the clique formed by adding Template:Mvar to Template:Mvar and removing the non-neighbors of Template:Mvar. However, some cliques of Template:Mvar may be generated in this way from more than one parent clique of Template:Math, so they eliminate duplicates by outputting a clique in Template:Mvar only when its parent in Template:Math is lexicographically maximum among all possible parent cliques. On the basis of this principle, they show that all maximal cliques in Template:Mvar may be generated in time Template:Math per clique, where Template:Mvar is the number of edges in Template:Mvar and Template:Mvar is the number of vertices. Template:Harvtxt improve this to Template:Math per clique, where Template:Mvar is the arboricity of the given graph. Template:Harvtxt provide an alternative output-sensitive algorithm based on fast matrix multiplication. Template:Harvtxt show that it is even possible to list all maximal cliques in lexicographic order with polynomial delay per clique. However, the choice of ordering is important for the efficiency of this algorithm: for the reverse of this order, there is no polynomial-delay algorithm unless P = NP.

On the basis of this result, it is possible to list all maximal cliques in polynomial time, for families of graphs in which the number of cliques is polynomially bounded. These families include chordal graphs, complete graphs, triangle-free graphs, interval graphs, graphs of bounded boxicity, and planar graphs.Template:Sfnp In particular, the planar graphs have Template:Math 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 sparse (having a number of edges at most a constant times the number of vertices) and closed under the operation of taking subgraphs.<ref name="CN85"/><ref name="ELS10"/>

Finding maximum cliques in arbitrary graphsEdit

It is possible to find the maximum clique, or the clique number, of an arbitrary n-vertex graph in time Template:Math 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 Template:Harvtxt solves this problem in time Template:Math. It is a recursive backtracking scheme similar to that of the Bron–Kerbosch algorithm, but is able to eliminate some recursive calls when it can be shown that the cliques found within the call will be suboptimal. Template:Harvtxt improved the time to Template:Math, and Template:Harvtxt improved it to Template:Math time, at the expense of greater space usage. Robson's algorithm combines a similar backtracking scheme (with a more complicated case analysis) and a dynamic programming technique in which the optimal solution is precomputed for all small connected subgraphs of the complement graph. These partial solutions are used to shortcut the backtracking recursion. The fastest algorithm known today is a refined version of this method by Template:Harvtxt which runs in time Template:Math.Template:Sfnp

There has also been extensive research on heuristic algorithms for solving maximum clique problems without worst-case runtime guarantees, based on methods including branch and bound,<ref>Template:Harvtxt; Template:Harvtxt; Template:Harvtxt; Template:Harvtxt; Template:Harvtxt; Template:Harvtxt; Template:Harvtxt; Template:Harvtxt.</ref> local search,<ref>Template:Harvtxt; Template:Harvtxt.</ref> greedy algorithms,<ref>Template:Harvtxt; Template:Harvtxt.</ref> and constraint programming.Template:Sfnp Non-standard computing methodologies that have been suggested for finding cliques include DNA computing<ref>Template:Harvtxt. Although the title refers to maximal cliques, the problem this paper solves is actually the maximum clique problem.</ref> and adiabatic quantum computation.Template:Sfnp The maximum clique problem was the subject of an implementation challenge sponsored by DIMACS in 1992–1993,Template:Sfnp and a collection of graphs used as benchmarks for the challenge, which is publicly available.<ref>DIMACS challenge graphs for the clique problem Template:Webarchive, accessed 2009-12-17.</ref>

Special classes of graphsEdit

File:Permutation graph.svg
In this permutation graph, the maximum cliques correspond to the longest decreasing subsequences (4,3,1) and (4,3,2) of the defining permutation.

Planar graphs, 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.<ref name="CN85"/> In particular, for planar graphs, any clique can have at most four vertices, by Kuratowski's theorem.<ref name="planar"/>

Perfect graphs are defined by the properties that their clique number equals their chromatic number, and that this equality holds also in each of their induced subgraphs. For perfect graphs, it is possible to find a maximum clique in polynomial time, using an algorithm based on semidefinite programming.Template:Sfnp However, this method is complex and non-combinatorial, and specialized clique-finding algorithms have been developed for many subclasses of perfect graphs.Template:Sfnp In the complement graphs of bipartite graphs, Kőnig's theorem allows the maximum clique problem to be solved using techniques for matching. In another class of perfect graphs, the permutation graphs, a maximum clique is a longest decreasing subsequence 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.<ref>Template:Harvtxt, p. 159.</ref> Template:Harvtxt provide an alternative quadratic-time algorithm for maximum cliques in comparability graphs, a broader class of perfect graphs that includes the permutation graphs as a special case.Template:Sfnp In chordal graphs, the maximal cliques can be found by listing the vertices in an elimination ordering, and checking the clique neighborhoods of each vertex in this ordering.<ref>Template:Harvtxt, Lemma 4.5, p. 19.</ref>

In some cases, these algorithms can be extended to other, non-perfect, classes of graphs as well. For instance, in a circle graph, 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.<ref>Template:Harvtxt; Template:Harvtxt, p. 247.</ref> Similarly, in a unit disk graph (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.Template:Sfnp

File:Planted clique 15,32.svg
A random graph with a planted clique

The algorithmic problem of finding a maximum clique in a random graph drawn from the Erdős–Rényi model (in which each edge appears with probability Template:Math, independently from the other edges) was suggested by Template:Harvtxt. 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 Template:Math. This is a quasi-polynomial time bound.Template:Sfnp Although the clique number of such graphs is usually very close to Template:Math, simple greedy algorithms as well as more sophisticated randomized approximation techniques only find cliques with size Template:Math, half as big. The number of maximal cliques in such graphs is with high probability exponential in Template:Math, which prevents methods that list all maximal cliques from running in polynomial time.Template:Sfnp Because of the difficulty of this problem, several authors have investigated the planted clique problem, the clique problem on random graphs that have been augmented by adding large cliques.<ref>Template:Harvtxt, Example 18.2, pp. 362–363.</ref> While spectral methodsTemplate:Sfnp and semidefinite programmingTemplate:Sfnp can detect hidden cliques of size Template:Math, no polynomial-time algorithms are currently known to detect those of size Template:Math (expressed using little-o notation).Template:Sfnp

Approximation algorithmsEdit

Several authors have considered approximation algorithms 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.<ref>Template:Harvtxt; Template:Harvtxt; Template:Harvtxt.</ref>

Template:Harvtxt describes a polynomial time algorithm that finds a clique of size Template:Math in any graph that has clique number Template:Math for any constant Template:Mvar. By using this algorithm when the clique number of a given input graph is between Template:Math and Template:Math, switching to a different algorithm of Template:Harvtxt for graphs with higher clique numbers, and choosing a two-vertex clique if both algorithms fail to find anything, Feige provides an approximation algorithm that finds a clique with a number of vertices within a factor of Template:Math of the maximum. Although the approximation ratio of this algorithm is weak, it is the best known to date.<ref>Template:Harvtxt: "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.</ref> The results on hardness of approximation described below suggest that there can be no approximation algorithm with an approximation ratio significantly less than linear.

Lower boundsEdit

NP-completenessEdit

File:Sat reduced to Clique from Sipser.svg
The 3-CNF Satisfiability instance (x ∨ x ∨ y) ∧ (~x ∨ ~y ∨ ~y) ∧ (~x ∨ y ∨ y) reduced to Clique. The green vertices form a 3-clique and correspond to a satisfying assignment.<ref>Adapted from Template:Harvtxt</ref>

The clique decision problem is NP-complete. It was one of Richard Karp's original 21 problems shown NP-complete in his 1972 paper "Reducibility Among Combinatorial Problems".Template:Sfnp This problem was also mentioned in Stephen Cook's paper introducing the theory of NP-complete problems.Template:Sfnp Because of the hardness of the decision problem, the problem of finding a maximum clique is also NP-hard. If one could solve it, one could also solve the decision problem, by comparing the size of the maximum clique to the size parameter given as input in the decision problem.

Karp's NP-completeness proof is a many-one reduction from the Boolean satisfiability problem. It describes how to translate Boolean formulas in conjunctive normal form (CNF) into equivalent instances of the maximum clique problem.<ref>Template:Harvtxt gives essentially the same reduction, from 3-SAT instead of Satisfiability, to show that subgraph isomorphism is NP-complete.</ref> Satisfiability, in turn, was proved NP-complete in the Cook–Levin theorem. From a given CNF formula, Karp forms a graph that has a vertex for every pair Template:Math, where Template:Mvar is a variable or its negation and Template:Mvar is a clause in the formula that contains Template:Mvar. 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 Template:Math to Template:Math whenever Template:Math and Template:Mvar and Template:Mvar are not each other's negations. If Template:Mvar denotes the number of clauses in the CNF formula, then the Template:Mvar-vertex cliques in this graph represent consistent ways of assigning truth values to some of its variables in order to satisfy the formula. Therefore, the formula is satisfiable if and only if a Template:Mvar-vertex clique exists.Template:Sfnp

Some NP-complete problems (such as the travelling salesman problem in planar graphs) may be solved in time that is exponential in a sublinear function of the input size parameter Template:Mvar, significantly faster than a brute-force search.<ref>Template:Harvtxt.</ref> However, it is unlikely that such a subexponential time bound is possible for the clique problem in arbitrary graphs, as it would imply similarly subexponential bounds for many other standard NP-complete problems.Template:Sfnp

Circuit complexityEdit

File:Monotone circuit for 3-clique.svg
A monotone circuit to detect a Template:Mvar-clique in an Template:Mvar-vertex graph for Template:Math and Template:Math. Each input to the circuit encodes the presence or absence of a particular (red) edge in the graph. The circuit uses one internal and-gate to detect each potential Template:Mvar-clique.

The computational difficulty of the clique problem has led it to be used to prove several lower bounds in circuit complexity. The existence of a clique of a given size is a monotone graph property, meaning that, if a clique exists in a given graph, it will exist in any supergraph. Because this property is monotone, there must exist a monotone circuit, using only and gates and or gates, to solve the clique decision problem for a given fixed clique size. However, the size of these circuits can be proven to be a super-polynomial function of the number of vertices and the clique size, exponential in the cube root of the number of vertices.<ref>Template:Harvtxt. For earlier and weaker bounds on monotone circuits for the clique problem, see Template:Harvtxt and Template:Harvtxt.</ref> Even if a small number of NOT gates are allowed, the complexity remains superpolynomial.<ref>Template:Harvtxt.</ref> Additionally, the depth of a monotone circuit for the clique problem using gates of bounded fan-in must be at least a polynomial in the clique size.<ref>Template:Harvtxt used communication complexity to prove this result.</ref>

Decision tree complexityEdit

File:Decision tree for 3-clique no arrowheads.svg
A simple decision tree to detect the presence of a 3-clique in a 4-vertex graph. It uses up to 6 questions of the form "Does the red edge exist?", matching the optimal bound n(n − 1)/2.

The (deterministic) decision tree complexity of determining a graph property is the number of questions of the form "Is there an edge between vertex Template:Mvar and vertex Template:Mvar?" that have to be answered in the worst case to determine whether a graph has a particular property. That is, it is the minimum height of a Boolean decision tree for the problem. There are Template:Math possible questions to be asked. Therefore, any graph property can be determined with at most Template:Math questions. It is also possible to define random and quantum decision tree complexity of a property, the expected number of questions (for a worst case input) that a randomized or quantum algorithm needs to have answered in order to correctly determine whether the given graph has the property.<ref>See Template:Harvtxt, Chapter 12, "Decision trees", pp. 259–269.</ref>

Because the property of containing a clique is monotone, it is covered by the Aanderaa–Karp–Rosenberg conjecture, which states that the deterministic decision tree complexity of determining any non-trivial monotone graph property is exactly Template:Math. For arbitrary monotone graph properties, this conjecture remains unproven. However, for deterministic decision trees, and for any Template:Mvar in the range Template:Math, the property of containing a Template:Mvar-clique was shown to have decision tree complexity exactly Template:Math by Template:Harvtxt. Deterministic decision trees also require exponential size to detect cliques, or large polynomial size to detect cliques of bounded size.<ref>Template:Harvtxt.</ref>

The Aanderaa–Karp–Rosenberg conjecture also states that the randomized decision tree complexity of non-trivial monotone functions is Template:Math. The conjecture again remains unproven, but has been resolved for the property of containing a Template:Mvar clique for Template:Math. This property is known to have randomized decision tree complexity Template:Math.<ref>For instance, this follows from Template:Harvtxt.</ref> For quantum decision trees, the best known lower bound is Template:Math, but no matching algorithm is known for the case of Template:Math.<ref>Template:Harvtxt; Template:Harvtxt.</ref>

Fixed-parameter intractabilityEdit

Parameterized complexity is the complexity-theoretic study of problems that are naturally equipped with a small integer parameter Template:Mvar and for which the problem becomes more difficult as Template:Mvar increases, such as finding Template:Mvar-cliques in graphs. A problem is said to be fixed-parameter tractable if there is an algorithm for solving it on inputs of size Template:Mvar, and a function Template:Mvar, such that the algorithm runs in time Template:Math. That is, it is fixed-parameter tractable if it can be solved in polynomial time for any fixed value of Template:Mvar and moreover if the exponent of the polynomial does not depend on Template:Mvar.<ref>Template:Harvtxt. Technically, there is usually an additional requirement that Template:Mvar be a computable function.</ref>

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

Template:Harvtxt showed that finding Template:Mvar-vertex cliques cannot be done in time Template:Math unless the exponential time hypothesis fails. Again, this provides evidence that no fixed-parameter tractable algorithm is possible.Template:Sfnp

Although the problems of listing maximal cliques or finding maximum cliques are unlikely to be fixed-parameter tractable with the parameter Template:Mvar, they may be fixed-parameter tractable for other parameters of instance complexity. For instance, both problems are known to be fixed-parameter tractable when parametrized by the degeneracy of the input graph.<ref name="ELS10">Template:Harvtxt.</ref>

Hardness of approximationEdit

File:Cube-face-intersection-graph.svg
A graph of compatibility relations among 2-bit samples of 3-bit proof strings. Each maximal clique (triangle) in this graph represents all ways of sampling a single 3-bit string. The proof of inapproximability of the clique problem involves induced subgraphs of analogously defined graphs for larger numbers of bits.

Weak results hinting that the clique problem might be hard to approximate have been known for a long time. Template:Harvtxt observed that, because the clique number takes on small integer values and is NP-hard to compute, it cannot have a fully polynomial-time approximation scheme, 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 probabilistically checkable proofs. They used these connections to prove hardness of approximation results for the maximum clique problem.<ref>Template:Harvtxt; Template:Harvtxt; Template:Harvtxt.</ref> After many improvements to these results it is now known that, for every real number Template:Math, there can be no polynomial time algorithm that approximates the maximum clique to within a factor better than Template:Math, unless P = NP.<ref>Template:Harvtxt showed inapproximability for this ratio using a stronger complexity theoretic assumption, the inequality of NP and ZPP. Template:Harvtxt described more precisely the inapproximability ratio, but with an even stronger assumption. Template:Harvtxt derandomized the construction weakening its assumption to P ≠ NP.</ref>

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

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

NotesEdit

Template:Reflist

ReferencesEdit

Surveys and textbooksEdit

Template:Refbegin

Template:Refend

Research articlesEdit

Template:Refbegin

Template:Refend

Retrieved from "https://zalansite.site/mediawiki/index.php?title=Clique_problem&oldid=168147"