Editing Clique problem (section)

==Definitions==
{{Main|Clique (graph theory)}}
[[File:6n-graf-clique.svg|thumb|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 [[vertex (graph theory)|vertices]] and a set of [[unordered pair]]s of vertices, which are called [[edge (graph theory)|edges]]. By convention, in algorithm analysis, the number of vertices in the graph is denoted by {{mvar|n}} and the number of edges is denoted by {{mvar|m}}. A [[clique (graph theory)|clique]] in a graph {{mvar|G}} is a [[complete graph|complete]] [[Glossary of graph theory#Subgraphs|subgraph]] of {{mvar|G}}. That is, it is a subset {{mvar|K}} of the vertices such that every two vertices in {{mvar|K}} are the two endpoints of an edge in {{mvar|G}}. A [[maximal clique]] is a clique to which no more vertices can be added. For each vertex {{mvar|v}} that is not part of a maximal clique, there must be another vertex {{mvar|w}} that is in the clique and non-adjacent to {{mvar|v}}, preventing {{mvar|v}} from being added to the clique. A [[maximum clique]] is a clique that includes the largest possible number of vertices. The clique number {{math|''ω''(''G'')}} is the number of vertices in a maximum clique of {{mvar|G}}.<ref name="bbpp"/>

Several closely related clique-finding problems have been studied.<ref name="v02p09">{{harvtxt|Valiente|2002}}; {{harvtxt|Pelillo|2009}}.</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.{{sfnp|Pelillo|2009}} As well as the problem of optimizing the sum of weights, other more complicated bicriterion optimization problems have also been studied.{{sfnp|Sethuraman|Butenko|2015}}
*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.{{sfnp|Valiente|2002}}
*In the {{mvar|k}}-clique problem, the input is an undirected graph and a number {{mvar|k}}. The output is a clique with {{mvar|k}} vertices, if one exists, or a special value indicating that there is no {{mvar|k}}-clique otherwise. In some variations of this problem, the output should list all cliques of size {{mvar|k}}.<ref name="CN85"/>
*In the clique decision problem, the input is an undirected graph and a number {{mvar|k}}, and the output is a [[truth value|Boolean value]]: true if the graph contains a {{mvar|k}}-clique, and false otherwise.{{sfnp|Cormen|Leiserson|Rivest|Stein|2001}}
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.{{sfnp|Cormen|Leiserson|Rivest|Stein|2001}}

The clique problem and the [[independent set problem]] are complementary: a clique in {{mvar|G}} is an independent set in the [[complement graph]] of {{mvar|G}} and vice versa.<ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, Exercise 34-1, p.&nbsp;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 graph]]s<ref name="planar">{{harvtxt|Papadimitriou|Yannakakis|1981}}; {{harvtxt|Chiba|Nishizeki|1985}}.</ref> while the independent set problem remains NP-hard on planar graphs.{{sfnp|Garey|Johnson|Stockmeyer|1976}}