Yixin Cao (操宜新) Associate Professor Department of Computing Hong Kong Polytechnic University Hong Kong, China * yi – in.c – o@polyu.edu.hk (substitute '–' with human intelligence) +852 3400-3195 PQ706, Mong Man Wai Building

Research

Publications     Slides     Google Scholar     DBLP     Curriculum Vitae                              Research Group    

I am mainly working on algorithmic graph theory and its applications. I'm also interested in theoretical computer science in the broadest sense.

• algorithmic & structural graph theory and graph classes,
• fine-grained complexity and algorithm design,
• combinatorial optimization, and
• their applications in social networks and bioinformatics.

Events (author–organizer–speaker):
FAW'19 ++ 算法与复杂性 ++ CanaDAM'19 ++ Worker'19 ++ GTCA'19 ++ ICDCS'19 ++ 理论计算机科学年会 ++ ISAAC'19
TAMC'20 ++ WG'20 ++ 运筹学会年会 ++ IPEC'20 ++ ISAAC'20 ++ WEPA'20
SOSA'21 ++ CanaDAM'21 ++ WG'21 ++ IPEC'21
ICALP'22 ++ TAMC'22 ++ COCOON'22
WG'23 ++ 算法与复杂性 ++ FPT Fest ++ 理论计算机科学年会 ++ MFCS'23 ++ ESA'23 ++ ISAAC'23 ++ COCOON'23
LATIN'24 ++ TAMC'24 ++ 理论计算机科学年会 ++ ICML'24 ++ COCOON'24 ++ MFCS'24 ++ ESA'24

Teaching (current)

F2024: COMP2011, Data structures.

Grants (PI only)

• Forbidden structures of circular-arc graphs and their algorithmic applications, PolyU, 09/2015--08/2017
• Theoretical analysis of heuristics in big data, NLSDE, 07/2016–07/2018.
• Efficient algorithms for graph modification problems, RGC, 01/2016–12/2018.
• Combinatorial and algorithmic studies on cycles, NSFC, 01/2016–12/2019.
• Graph algorithms based on modular decomposition, RGC, 01/2017–12/2019.
• Super-polynomial approximation of graph problems, RGC, 01/2018–12/2020.
• Algorithmic study on chordal and related graphs, NSFC, 01/2020–12/2023.
• Approximation algorithms for phylogenetic networks, RGC, 01/2021–12/2023.
• (Parameterized) complexity of graph edge editing problems, NSFC, 01/2024–12/2027.

News

• October 2024, paper "Self-complementary (pseudo-)split graphs" accepted by Graphs and Combinatorics.
• August 2024, visit Jagiellonian University (Uniwersytet Jagielloński) and Warsaw University of Technology.
• June 2024, paper "Modification problems toward proper (Helly) circular-arc graphs" accepted by Information and Computation.
• June 2024, paper "Switching classes: characterization and computation" accepted by MFCS 2024.
• May 2024, paper "Minimum sum vertex cover: kernelization and parameterized algorithms" accepted by COCOON 2024.
• May 2024, Jing Huang visits us from the University of Victoria.
• May 2024, paper "Combinatorial approximations for cluster deletion: simpler, faster, and better" accepted by ICML 2024.
• April 2024, Tomasz Krawczyk visits us from Warsaw University of Technology.
• December 2023, paper "Self-complementary (pseudo-)split graphs" accepted by LATIN 2024.
• August 2023, visit Jagiellonian University (Uniwersytet Jagielloński).
• June 2023, paper "Modification problems toward proper (Helly) circular-arc graphs" accepted by MFCS 2023.
• June 2023, paper "Enumerating maximal induced subgraphs" accepted by ESA 2023.
• August 2023, visit University of Electronic Science and Technology of China.
• May 2023, Miss Ying Xu joined our group.
• Apr. 2022, paper "Graph searches and their end vertices" accepted by Algorithmica.
• Apr. 2022, paper "(Sub)linear kernels for edge modification problems toward structured graph classes" accepted by Algorithmica.
• Jan. 2022, paper "A 5k-vertex kernel for P₂-packing" accepted by Theoretical Computer Science.
• Dec. 2021, Mr. Haowei Chen joined our group.
• Oct. 2021, paper "A polynomial kernel for diamond-free editing" accepted by Algorithmica.
• Aug. 2021, paper "Polynomial kernels for paw-free edge modification problems" accepted by Theoretical Computer Science.
• July 2021, paper "Improved kernels for edge modification problems" accepted by IPEC'21.
• July 2021, paper "End vertices of graph searches on bipartite graphs" accepted by Information Processing Letters.
• May 2021, to co-orginize a minisymposium on "Algorithms for interval graphs and related families" at CanaDAM 2021.
• Apr. 2021, paper "Complementation in t-perfect graphs" accepted by WG'21.
• Oct. 2020, paper "Recognizing (unit) interval graphs by zigzag graph searches" accepted by SOSA'21.
• Aug. 2020, taught the CCF Summer School on algrothmic graph theory.
• Apr. 2020, paper "Characterization and linear-time recognition of paired threshold graphs" accepted by WG'20.
• Feb. 2020, paper "Polynomial kernels for paw-free edge modification problems" accepted by TAMC'20.
• Dec. 2019, paper "Minimum fill-in: Inapproximability and almost tight lower bounds" accepted by Information and Computation.
• Oct. 2019, The Algorithmica Special Issue on Computing and Combinatorics is finally published.
• Aug. 2019, paper "Graph searches and their end vertices" accepted by ISAAC 2019.
• Aug. 2019, Mr. Shenghua Wang joined our group.
• Aug. 2019, visited Institute of Logic and Computation, TU Wien, Vienna, Austria.
• July 2019, visited Institute for Basic Science, Korean.
• June 2019, taught a mini-course "graph algorithms based on modular decomposition" at Lanzhou University.
• Jan. 2019, visited Hangzhou Dianzi University.
• Sep. 2018, visited Sun Yat-sen University.
• Aug. 2018, visited Lanzhou University.

* Hong Kong has no postal code, so put 0000 if you're stubbornly required to.