using as a subroutine an algorithm for the maximal clique listing problem, because the maximum clique must be included among all the maximal cliques. In the -clique problem, the input is an undirected graph and a number . The output is a clique with vertices, if one exists, or a special value indicating that there is no -clique otherwise. In some variations of this problem, the output should list all cliques of size . In the clique decision problem, the input is an undirected graph and a number , and the output is a Boolean value: true if the graph contains a -clique, and false otherwise. 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. The clique problem and the independent set problem are complementary: a clique in is an independent set in the complement graph of and vice versa. 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 while the independent set problem remains NP-hard on planar graphs. Algorithms Finding a single maximal clique 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. 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. 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 that this loop examines, add to the clique if it is adjacent