The Chinese University of Hong Kong
Department of Computer Science and Engineering

Regular Department Seminar Series

Title: New and Simple FPT Algorithms for Vertex Covers
Date: October 20, 2017 (Friday)
Time: 4:00 p.m. - 5:00 p.m.
Venue: Room 121, 1/F, Ho Sin-hang Engineering Building,
The Chinese University of Hong Kong,
Shatin, N.T.
Speaker: Prof. CAI Leizhen
Department of Computer Science and Engineering
The Chinese University of Hong Kong



An FPT (fixed-parameter tractable) algorithm confines the exponential running time of the algorithm by a parameter k, and therefore can solve NP-hard problems effectively when k is relatively small. The classical Vertex Cover problem requires us to determine whether a graph contains k vertices that cover all edges. In spite of its NP-hardness, the problem admits FPT algorithms, and the current fastest FPT algorithm solves the problem effectively for graphs with billions of vertices as far as k < 200. In comparison, an exhaustive search algorithm for the problem can hardly handle a graph with 100 vertices even for k = 10.

In this talk, we present three new and simple FPT algorithms for the Vertex Cover problem. For this purpose, we explore structural properties of vertex covers and use these properties to obtain FPT algorithms using colour coding, iterative compression, and indirect certificate methods. These new algorithms provide us with new insight into this classical problem.



Prof. Cai received his PhD degree from the University of Toronto in 1992 and his main research interest resides in FPT algorithms for graph problems. He is particularly keen in designing simple and elegant algorithms, and is a co-inventor of an innovative random separation method for designing FPT algorithms. He has also initiated the study of structural parameters for FPT algorithms.


Enquiries: Ms Ricola Lo at tel 3943 8439

For more information, please refer to