Plenary
Lecture
The Maximum Clique Problem
Professor Etsuji Tomita
Advanced Algorithms Research Laboratory
Department of Information and Communication Engineering
The University of ElectroCommunications
Tokyo, JAPAN
Email:
tomita@ice.uec.ac.jp
Abstract:
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
NPcomplete by R. Karp. Therefore, it is strongly
believed that the maximum clique problem is not solvable
easily, i.e., it is not solvable in polynomialtime.
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 branchandbound algorithms in which
appropriate bounding condition is most crucial. The
stepbystep 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.
Brief Biography of the Speaker:
Etsuji Tomita received his B. Eng. and Dr. Eng. degrees
in Electronics Engineering from Tokyo Institute of
Technology, Japan, in 1966 and 1971, respectively. Then
he was with the faculties of Tokyo Institute of
Technology, and was appointed Associate Professor and
subsequently Professor at the University of
ElectroCommunications, Japan. Since 2008, he has been
Professor Emeritus at the University of
ElectroCommunications and Professor at the Research and
Development Initiative of Chuo University. He also
teaches at Hokkaido University as a parttime lecturer.
He served as the Head of the department of Information
and Communication Engineering, and the Head of the
Advanced Algorithms Research Laboratory at UEC.
His research interests include design and analysis of
computer algorithms, combinatorial optimization and its
application to practical problems, algorithmic learning
theory, and theory of automata and formal languages.
His academic contributions include Editor of IEICE
(Institute of Electronics, Information and Communication
Engineers) and EditorinChief of IPSJ (Information
processing Society of Japan), Local Arrangement Chair of
ALT (Algorithmic Learning Theory), Chair of SIG
Mathematical Modeling and Problem Solving of IPSJ,
Program Committee Chair of ALT 2005, and he served as a
Guest Editor of Theoretical Computer Science, Conference
Chair of ICGI (International Colloquium on Grammatical
Inference) 2006, Director of IPSJ, Chair of Computer
Science Domain of IPSJ, and Councilor of JSAI (The
Japanese Society for Artificial Intelligence). He is
presently a member of Steering Committee of ICGI.
He was given the Yonezawa Award of IECE, the Funai
Information Technology Prize, and the Contribution Award
of SIG MPS of IPSJ, and is presently a Fellow of IEICE
and IPSJ.
He is a coauthor of two papers that were given
Yamashita Research Award of IPSJ, and of a paper that
was given Encouraging Award of Computer Science Domain
of IPSJ.
