CAI Leizhen, CUHK CSE

Prof. CAI Leizhen 蔡雷震

Ph.D., University of Toronto, 1992 (supervisor: Derek Corneil)
M.Sc., University of Victoria, 1988 (supervisor: John Ellis)
B.Sc., Zhejiang University, 1982
Photo
Professor Emeritus (2022)
Department of Computer Science and Engineering
The Chinese University of Hong Kong
Shatin, Hong Kong, China
Email: lcai@cse.cuhk.edu.hk

中大三十年 (30 years in CUHK) (照片, 简历)

Research Interests: FPT-algorithms, graph algorithms, and graph theory.

Theorem [Cai 2018]. Every yes-instance of k-Vertex Cover has a certificate with at most k/3 vertices.

My randomized algorithm for k-Vertex Cover, where N(M) denotes the open neighborhood of marked vertices:

Randomly mark each vertex and output N(M).
Teaching:
CSCI5320 Topics in Graph Algorithms   Random Separation
CSCI3160 Design and Analysis of Algorithms   Finale (courtesy of MA Siu Tong)

Other courses:
ENGG1410 Engineering Mathematics
CSCI2100 Discrete Mathematics
CSCI2110 Data Structures
ENGG2440 Discrete Mathematics for Engineers
ESTR3104 Design and Analysis of Algorithms (Elite Class)
CSC3640 Introduction to Theoretical Computer Science
CSC6160 Algorithmic Graph Theory
CSC7120 Computational Complexity

Also taught Computability and Complexity (CSC364) at University of Toronto,
a graduate course Parameterized Complexity at Tsinghua University, and
an undergraduate course Programming in Pascal at Zhejiang University.

Hobby: Stone carving


Representative Publications:
  1. L. Cai, Vertex Covers Revisited: Indirect Certificates and FPT Algorithms, revision of arXiv:1807.11339, 2025.

  2. L. Cai and J. Ye, Two Edge-Disjoint Paths with Length Constraints, Theoretical Computer Science, Vol 795 275-284, 2019.

  3. L. Cai and Y. Cai, Incompressibility of H-Free Edge Modification Problems, Invited paper of IPEC 2013, Algorithmica 71(3) 731-757, 2015.

  4. M. Xiao, L. Cai, and A.C.C. Yao, Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem, Algorithmica Vol 59 510-520, 2011.

  5. L. Cai, Parameterized Complexity of Cardinality Constrained Optimization Problems, the Computer Journal 51(1) 102-121, 2008.

  6. L. Cai, S.M. Chan and S.O. Chan, Random Separation: a New Method for Solving Fixed-Cardinality Optimization Problems, IWPEC 2006, LNCS 4169, pp. 239-250, 2006.

  7. L. Cai, Parameterized Complexity of Vertex Colouring, Discrete Applied Mathematics, 127(3) 415-429, 2003.

  8. L. Cai, Fixed-parameter tractability of graph modification problems for hereditary properties, Information Processing Letters, 58, 171-176, 1996.

  9. L. Cai and D.G. Corneil, Tree Spanners, SIAM Journal on Discrete Mathematics, 8(3), 359-387, 1995.