In
graph analysis and
graph theory, a k-clique is a group of k
nodes, where each node in the
clique is connected to every other node in the clique. The k-clique problem at the present is in
class NP, which means that there is no solution to finding cliques in
polynomial time, but if a clique is found in the graph, it can be verified in polynomial time. The
Turing Machine described below can verify the k-clique in polynomial time.
TM KClique = "on input <
G ,
k >, where
G is a graph:
1: Nondeterministically select a set of nodes
k nodes from
G .
2: Test if
G contains all edges connecting the nodes in set
k .
3: If all nodes in
k are connected,
accept, else
reject.
From
Michael Sipser's book
Introduction to the Theory of Computation.