the problem of finding the maximum common induced subgraph of two graphs to the problem of finding a maximum clique in their product. In automatic test pattern generation, finding cliques can help to bound the size of a test set. In bioinformatics, clique-finding algorithms have been used to infer evolutionary trees, predict protein structures, and find closely interacting clusters of proteins. Listing the cliques in a dependency graph is an important step in the analysis of certain random processes. In mathematics, Keller's conjecture on face-to-face tiling of hypercubes was disproved by , who used a clique-finding algorithm on an associated graph to find a counterexample. Definitions 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 and the number of edges is denoted by . A clique in a graph is a complete subgraph of . That is, it is a subset of the vertices such that every two vertices in are the two endpoints of an edge in . A maximal clique is a clique to which no more vertices can be added. For each vertex that is not part of a maximal clique, there must be another vertex that is in the clique and non-adjacent to , preventing from being added to the clique. A maximum clique is a clique that includes the largest possible number of vertices. The clique number is the number of vertices in a maximum clique of . Several closely related clique-finding problems have been studied. 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. 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. As well as the problem of optimizing the sum of weights, other more complicated bicriterion optimization problems have also been studied. 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