CINXE.COM

<?xml version="1.0" encoding="UTF-8"?> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> <html xml:lang="utf-8"> <head> <title>Yixin Cao</title> <style type="text/css"> body { font: 16px/1.5 "Palatino Linotype", Palatino, serif; } li.hidden { display: none; hr { max-width: 100px; margin: 0px; } } </style> <meta name="Author" content="Yixin Cao" />  <script type="text/javascript" src="http://www4.comp.polyu.edu.hk/tracking41.js"></script> <noscript type="text/javascript" src="http://www4.comp.polyu.edu.hk/tracking42.js"></noscript> </head> <script async src="https://www.googletagmanager.com/gtag/js?id=G-Z9LCGKY6RP"></script> <script> window.dataLayer = window.dataLayer || []; function gtag(){dataLayer.push(arguments);} gtag('js', new Date()); gtag('config', 'G-Z9LCGKY6RP'); window.onload=function(){ var obt=document.getElementById("bt"); obt.onclick=function(){ var pArys=document.getElementsByClassName("hidden"); for(var i = 1; i <= pArys.length; i++){ var odiv=document.getElementById("p"+i); if(odiv.style.display!="none"){ odiv.style.display="none"; obt.value="older"; } else{ odiv.style.display="block"; obt.value="latest"; } } } } </script> <body> <table border=0> <tr> <td width=50></td> <td> <center> <h1>Yixin Cao (操宜新) </h1> Associate Professor <a href="http://www.comp.polyu.edu.hk/">Department of Computing</a> <a href="http://www.polyu.edu.hk/">Hong Kong Polytechnic University</a> Hong Kong, China <a href="#zipcode">*</a> yi – in.c – o@polyu.edu.hk (substitute '–' with human intelligence) +852 3400-3195 PQ706, <a href="http://www.comp.polyu.edu.hk/en-us/contact-us">Mong Man Wai Building</a>  </td> <td width=230></td> <td><img src="profile.png" height="260"></td> </tr> </table>  <hr align="left" width="1000"> <h2>Research</h2>  <a href="pub.htm">Publications</a>     <a href="slides.htm">Slides</a>     <a href="http://scholar.google.com/citations?hl=en&user=vnVm31kAAAAJ">Google Scholar</a>     <a href="https://dblp.uni-trier.de/pers/hy/c/Cao_0001:Yixin">DBLP</a>     <a href="cv_yixin.pdf">Curriculum Vitae</a>                              <a href="group.htm">Research Group</a>     I am mainly working on algorithmic graph theory and its applications. I'm also interested in theoretical computer science in the broadest sense. <ul> <li>algorithmic & structural graph theory and graph classes,</li> <li>fine-grained complexity and algorithm design,</li> <li>combinatorial optimization, and</li> <li>their applications in social networks and bioinformatics.</li> </ul>  Events (author–organizer–speaker):  <a href="https://icalp2022.irif.fr/">ICALP'22</a> ++ <a href="https://lxy.tjut.edu.cn/TAMC2022.htm">TAMC'22</a> ++ <a href="http://cocoon-conference.org/2022/">COCOON'22</a> <a href="https://events.unifr.ch/wg2023/">WG'23</a> ++ <a href="https://www.cs.sdu.edu.cn/">算法与复杂性</a> ++ <a href="https://www.uib.no/en/rg/algo/160260/fpt-fest-2023-honour-mike-fellows"> FPT Fest</a> ++ <a href="http://cs.scnu.edu.cn/">理论计算机科学年会</a> ++ <a href="https://mfcs2023.labri.fr/">MFCS'23</a> ++ <a href="https://algo-conference.org/2023/esa/">ESA'23</a> ++ <a href="https://www.kurims.kyoto-u.ac.jp/isaac/isaac2023/">ISAAC'23</a> ++ <a href="https://theory.utdallas.edu/COCOON2023/">COCOON'23</a> <a href="https://latin2024.cmm.uchile.cl/">LATIN'24</a> ++ <a href="https://tamc2024.comp.polyu.edu.hk/">TAMC'24</a> ++ <a href="https://conf.ccf.org.cn/web/api/m1220009735990939648171091458774.action">理论计算机科学年会</a> ++ <a href="https://icml.cc/Conferences/2024">ICML'24</a> ++ <a href="https://anl.sjtu.edu.cn/cocoon2024/">COCOON'24</a> ++ <a href="http://www.mfcs.sk/">MFCS'24</a> ++ <a href="https://algo-conference.org/2024/esa/">ESA'24</a> <a href="https://cccg-wads-2025.eecs.yorku.ca/Home.html">WADS'25</a> <h2>Teaching (current)</h2>  S2025: COMP3022, Algorithm Engineering. <h2><a name="TOC-Grants"></a>Grants (PI only)</h2> <ul> <li>Forbidden structures of circular-arc graphs and their algorithmic applications, PolyU, 09/2015--08/2017</li> <li>Theoretical analysis of heuristics in big data, <a href="http://www.nlsde.buaa.edu.cn/" target="_blank" rel="nofollow">NLSDE</a>, 07/2016–07/2018.</li> <li>Efficient algorithms for graph modification problems, <a href="http://www.ugc.edu.hk/eng/rgc/" target="_blank" rel="nofollow">RGC</a>, 01/2016–12/2018.</li> <li>Combinatorial and algorithmic studies on cycles, <a href="http://www.nsfc.gov.cn/publish/portal1/" target="_blank" rel="nofollow">NSFC</a>, 01/2016–12/2019.</li> <li>Graph algorithms based on modular decomposition, <a href="http://www.ugc.edu.hk/eng/rgc/" target="_blank" rel="nofollow">RGC</a>, 01/2017–12/2019.</li> <li> Super-polynomial approximation of graph problems, <a href="http://www.ugc.edu.hk/eng/rgc/" target="_blank" rel="nofollow">RGC</a>, 01/2018–12/2020.</li> <li> Algorithmic study on chordal and related graphs, <a href="http://www.nsfc.gov.cn/publish/portal1/" target="_blank" rel="nofollow">NSFC</a>, 01/2020–12/2023.</li> <li> Approximation algorithms for phylogenetic networks, <a href="http://www.ugc.edu.hk/eng/rgc/" target="_blank" rel="nofollow">RGC</a>, 01/2021–12/2023.</li> <li> (Parameterized) complexity of graph edge editing problems, <a href="http://www.nsfc.gov.cn/publish/portal1/" target="_blank" rel="nofollow">NSFC</a>, 01/2024–12/2027.</li> </ul>  <h2><a name="TOC-News"></a>News</h2> <ul> <li>October 2024, paper "Self-complementary (pseudo-)split graphs" accepted by Graphs and Combinatorics.</li> <li>August 2024, visit Jagiellonian University (Uniwersytet Jagielloński) and Warsaw University of Technology.</li> <li>June 2024, paper "Modification problems toward proper (Helly) circular-arc graphs" accepted by Information and Computation.</li> <li>June 2024, paper "Switching classes: characterization and computation" accepted by MFCS 2024.</li> <li>May 2024, paper "Minimum sum vertex cover: kernelization and parameterized algorithms" accepted by COCOON 2024.</li> <li>May 2024, Jing Huang visits us from the University of Victoria.</li> <li>May 2024, paper "Combinatorial approximations for cluster deletion: simpler, faster, and better" accepted by ICML 2024.</li> <li id="p111" class="hidden">April 2024, Tomasz Krawczyk visits us from Warsaw University of Technology.</li> <li id="p110" class="hidden">December 2023, paper "Self-complementary (pseudo-)split graphs" accepted by LATIN 2024.</li> <li id="p109" class="hidden">August 2023, visit Jagiellonian University (Uniwersytet Jagielloński).</li> <li id="p108" class="hidden">June 2023, paper "Modification problems toward proper (Helly) circular-arc graphs" accepted by MFCS 2023.</li> <li id="p107" class="hidden">June 2023, paper "Enumerating maximal induced subgraphs" accepted by ESA 2023.</li> <li id="p106" class="hidden">August 2023, visit University of Electronic Science and Technology of China.</li> <li id="p105" class="hidden">May 2023, Miss Ying Xu joined our group.</li> <li id="p104" class="hidden">Apr. 2022, paper "Graph searches and their end vertices" accepted by Algorithmica.</li> <li id="p103" class="hidden">Apr. 2022, paper "(Sub)linear kernels for edge modification problems toward structured graph classes" accepted by Algorithmica.</li> <li id="p102" class="hidden">Jan. 2022, paper "A 5k-vertex kernel for P2-packing" accepted by Theoretical Computer Science.</li> <li id="p101" class="hidden">Dec. 2021, Mr. Haowei Chen joined our group.</li> <li id="p100" class="hidden">Oct. 2021, paper "A polynomial kernel for diamond-free editing" accepted by Algorithmica.</li> <li id="p99" class="hidden">Aug. 2021, paper "Polynomial kernels for paw-free edge modification problems" accepted by Theoretical Computer Science.</li> <li id="p98" class="hidden">July 2021, paper "Improved kernels for edge modification problems" accepted by IPEC'21.</li> <li id="p97" class="hidden">July 2021, paper "End vertices of graph searches on bipartite graphs" accepted by Information Processing Letters.</li> <li id="p96" class="hidden">May 2021, to co-orginize a minisymposium on "Algorithms for interval graphs and related families" at CanaDAM 2021.</li> <li id="p95" class="hidden">Apr. 2021, paper "Complementation in t-perfect graphs" accepted by WG'21.</li> <li id="p94" class="hidden">Oct. 2020, paper "Recognizing (unit) interval graphs by zigzag graph searches" accepted by SOSA'21.</li> <li id="p93" class="hidden">Aug. 2020, taught the CCF Summer School on algrothmic graph theory.</li> <li id="p92" class="hidden">Apr. 2020, paper "Characterization and linear-time recognition of paired threshold graphs" accepted by WG'20.</li> <li id="p91" class="hidden">Feb. 2020, paper "Polynomial kernels for paw-free edge modification problems" accepted by TAMC'20.</li> <li id="p90" class="hidden">Dec. 2019, paper "Minimum fill-in: Inapproximability and almost tight lower bounds" accepted by Information and Computation.</li> <li id="p89" class="hidden">Oct. 2019, The Algorithmica <a href="https://link.springer.com/journal/453/81/11/page/1" target="_blank" rel="nofollow">Special Issue on Computing and Combinatorics</a> is finally published.</li> <li id="p88" class="hidden">Aug. 2019, paper "Graph searches and their end vertices" accepted by ISAAC 2019.</li> <li id="p87" class="hidden">Aug. 2019, Mr. Shenghua Wang joined our group.</li> <li id="p86" class="hidden">Aug. 2019, visited Institute of Logic and Computation, TU Wien, Vienna, Austria.</li> <li id="p85" class="hidden">July 2019, visited Institute for Basic Science, Korean.</li> <li id="p84" class="hidden">June 2019, taught a mini-course "graph algorithms based on modular decomposition" at Lanzhou University.</li> <li id="p83" class="hidden">Jan. 2019, visited Hangzhou Dianzi University.</li> <li id="p82" class="hidden">Sep. 2018, visited Sun Yat-sen University.</li> <li id="p81" class="hidden">Aug. 2018, visited Lanzhou University.</li> <li > <input type="button" id="bt" value="older"/></li> </ul> <a id="zipcode">* Hong Kong has no postal code, so put 0000 if you're stubbornly required to.</a> </body>