#### 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
Professor
Department of Computer Science and Engineering
The Chinese University of Hong Kong |

**ABSTRACT:**
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.

**BIOGRAPHY:**
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
http://www.cse.cuhk.edu.hk/seminar.

**** ALL ARE WELCOME ****