Plenary lecture 2: the maximum clique problem
Etsuji Tomita · Annual Conference on Computers · 2010
A clique is a subgraph in which all pairs of vertices are mutually adjacent. A maximum clique is a clique of the maximum size. Thus, a maximum clique stands for a maximum collection of objects which are mutually related in some specified criterion. The so called maximum clique problem, or the complementary problem, the maximum independent set problem, is one of the original 21 problems shown to be NP-complete by R. Karp. Therefore, it is strongly believed that the maximum clique problem is not solvable easily, i.e., it is not solvable in polynomial-time. Nevertheless, much work has been done on this problem, experimentally and theoretically. It attracts much attention especially recently since it has found many practical applications. In this lecture, we are concerned with recent progress of efficient algorithms for finding a maximum clique. We focus on branch-and-bound algorithms in which appropriate bounding condition is most crucial. The step-by-step improvements on the bounding condition and their effectiveness are presented. Some algorithms for generating all maximal cliques are also shown. We give evaluations on these algorithms not only experimentally but also theoretically. We also give a natural condition in which the maximum clique problem can be proved to be polynomialtime solvable. In addition, we address successful applications of these algorithms to bioinformatics, image processing, data mining, and others.