Yixin Cao

Yixin Cao is an Associate Professor in the Department of Computing at Hong Kong Polytechnic University, Faculty of Engineering. He conducts research in theoretical computer science with a focus on algorithmic and structural graph theory, combinatorial optimization, and their applications. He leads a research group and is actively involved in the theoretical computer science community through publications, talks, and conference organization.

Research Interests:

• Algorithmic and structural graph theory, particularly on interval and circular-arc graphs
• Fine-grained complexity and parameterized algorithms
• Graph modification problems (editing, deletion, completion)
• Combinatorial optimization with applications in bioinformatics and social networks

His recent publications highlight a strong trend in characterizing complex graph classes (e.g., proper Helly circular-arc graphs, chordal circular-arc graphs) and developing efficient parameterized algorithms, especially kernelization techniques for graph editing problems. He frequently publishes in top venues such as Algorithmica, Theoretical Computer Science, ICALP, ESA, and MFCS.

Grants:

• PI, "(Parameterized) complexity of graph edge editing problems", NSFC, 01/2024–12/2027
• PI, "Approximation algorithms for phylogenetic networks", RGC, 01/2021–12/2023
• PI, "Algorithmic study on chordal and related graphs", NSFC, 01/2020–12/2023
• PI, "Super-polynomial approximation of graph problems", RGC, 01/2018–12/2020
• Multiple earlier grants from RGC, NSFC, and NLSDE on graph algorithms and complexity

Research Group:

• Advises graduate students including Ying Xu, Haowei Chen, and Shenghua Wang
• Hosts visiting researchers such as Tomasz Krawczyk (Warsaw University of Technology)
• Collaborates extensively with researchers in China and internationally