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.

Log in or register to write something here or to contact authors.