Publications of Yixin Cao

Books and Edited Special Issues of Journals

Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020), Yixin Cao, Siu-Wing Cheng, and Minming Li, editors. Schloss Dagstuhl - Leibniz-Zentrum für Informatik vol. 181 (2020) [publisher]

Proceedings of the 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), Yixin Cao and Marcin Pilipczuk, editors. Schloss Dagstuhl - Leibniz-Zentrum für Informatik vol. 180 (2020) [publisher]

Computing and Combinatorics, Yixin Cao and Jianer Chen, editors. Lecture Notes in Computer Science vol. 10392, Springer (2017) [publisher]

Journal Articles

(Sub)linear kernels for edge modification problems toward structured graph classes, with Gabriel Bathie, Nicolas Bousquet, Yuping Ke, and Théo Pierron. Algorithmica, 84:3338–3364 (2022) [publisher]

Graph searches and their end vertices, with Guozhen Rong, Jianxin Wang, and Zhifeng Wang. Algorithmica, 84:2642–2666 (2022) [publisher]

A 5k-vertex kernel for P2-packing, with Wenjun Li and Junjie Ye. Theoretical Computer Science, 910:1–13 (2022) [publisher]

A polynomial kernel for diamond-free editing, with Ashutosh Rai, R. B. Sandeep, and Junjie Ye. Algorithmica, 84:197–215 (2022) [publisher]

End vertices of graph searches on bipartite graphs, with Meibiao Zou, Zhifeng Wang, and Jianxin Wang. Information Processing Letters, 173, Article 106176 (2022) [publisher]

Polynomial kernels for paw-free edge modification problems, with Yuping Ke and Hanchun Yuan. Theoretical Computer Science, 891:1–12 (2021) [publisher]

Minimum fill-in: Inapproximability and almost tight lower bounds, with R. B. Sandeep. Information and Computation, 271, Article 104514 (2020) [publisher]

Vertex deletion problems on chordal graphs, with Yuping Ke, Yota Otachi, and Jie You. Theoretical Computer Science, 745:75–86 (2018) [publisher]

Unit interval vertex deletion: Fewer vertices are relevant, with Yuping Ke, Xiating Ouyang, and Jianxin Wang. Journal of Computer and System Sciences, 95:109–121 (2018) [publisher]

Unit interval editing is fixed-parameter tractable. Information and Computation, 253(1):109–126 (2017) [publisher]

Approximate association via dissociation, with Jianxin Wang and Jie You. Discrete Applied Mathematics, 219:202–209 (2017) [publisher]

Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree, with Jianer Chen, Wenjun Li, and Jianxin Wang. Information and Computation, 252:187–200 (2017) [publisher]

Forbidden induced subgraphs of normal Helly circular-arc graphs: Characterization and detection, with Luciano N. Grippo and Martin D. Safe. Discrete Applied Mathematics, 216(1):67–83 (2017) [publisher]

Chordal editing is fixed-parameter tractable, with Dániel Marx. Algorithmica, 75(1):118–137 (2016) [publisher]

On feedback vertex set: New measure and new structures, with Jianer Chen and Yang Liu. Algorithmica, 73(1):63–86 (2015) [publisher]

Edge deletion problems: Branching facilitated by modular decomposition, with Jianer Chen, Yunlong Liu, Jianxin Wang, and Jie You. Theoretical Computer Science, 573:63–70 (2015) [publisher]

Interval deletion is fixed-parameter tractable, with Dániel Marx. ACM Transactions on Algorithms, 11(3), Article 21 (2015) [publisher]

An O*(1.84k) parameterized algorithm for the multiterminal cut problem, with Jianer Chen and Jia-Hao Fan. Information Processing Letters, 114(4): 167–173 (2014) [publisher]

Cluster editing: Kernelization based on edge cuts, with Jianer Chen. Algorithmica, 64(1): 152–169 (2012) [publisher]

Referred Conference Papers

Improved kernels for edge modification problems, with Yuping Ke. Proceedings of the 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), 13:1–13:14. [arXiv][publisher]

Complementation in t-perfect graphs, with Shenghua Wang. Proceedings of the 47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2021), pp. 106–117. [arXiv][publisher]

Recognizing (unit) interval graphs by zigzag graph searches. Proceedings of the 4th Symposium on Simplicity in Algorithms (SOSA 2021), pp. 92–106. [arXiv][publisher]

Characterization and linear-time recognition of paired threshold graphs, with Guozhen Rong, Jianxin Wang. Proceedings of the 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2020), pp. 298–309. [arXiv][publisher]

Polynomial kernels for paw-free edge modification problems, with Yuping Ke and Hanchun Yuan. Proceedings of the 16th Annual Conference on Theory and Applications of Models of Computation (TAMC 2020), pp. 37–49. [arXiv][publisher]

Graph searches and their end vertices, with Guozhen Rong, Jianxin Wang, and Zhifeng Wang. Proceedings of the 30th International Symposium on Algorithms and Computation (ISAAC 2019), pp. 1:1–1:18. [arXiv][publisher]

A polynomial kernel for diamond-free editing, with Ashutosh Rai, R. B. Sandeep, and Junjie Ye. Proceedings of the 26th Annual European Symposium on Algorithms (ESA 2018), pp. 10:1–10:13. [arXiv][publisher]

Kernelization for P2-packing: A gerrymandering approach, with Wenjun Li and Junjie Ye. Proceedings of the 12th International Frontiers of Algorithmics Workshop (FAW 2018), pp. 140–153. [arXiv][publisher]

A naive algorithm for feedback vertex set. Proceedings of the first Symposium on Simplicity in Algorithms (SOSA 2018), pp. 1:1–1:8. [arXiv][publisher]

Vertex deletion problems on chordal graphs, with Yuping Ke, Yota Otachi, and Jie You. Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017), pp. 22:1–22:14. [arXiv][publisher]

Minimum fill-in: Inapproximability and almost tight lower bounds, with R. B. Sandeep. Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pp. 875–880. [arXiv][publisher]

Approximate association via dissociation, with Jianxin Wang and Jie You. Proceedings of the 42nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2016), LNCS vol. 9941, pp. 13–24. [arXiv][publisher]

Linear recognition of almost interval graphs. Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pp. 1096–1115. [arXiv (to be updated soon)][publisher]

A 2k-vertex kernel for maximum internal spanning tree, with Jianer Chen, Wenjun Li, and Jianxin Wang. Proceedings of the 14th International Symposium on Algorithms and Data Structures (WADS 2015), LNCS vol. 9214, pp. 495–505. [arXiv][publisher]

Unit interval editing is fixed-parameter tractable. Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), LNCS vol. 9134, pp. 306–317. [arXiv][publisher]

Direct and certifying recognition of normal Helly circular-arc graphs in linear time. Proceedings of the 8th International Frontiers of Algorithmics Workshop (FAW 2014), LNCS vol. 8497, pp. 13–24. [arXiv] [publisher]

The (un)supervised detection of overlapping communities as well as hubs and outliers via (Bayesian) NMF, with Xiaochun Cao, Xiao Wang, Di Jin, and Dongxiao He. Proceedings of the companion publication of the 23rd international conference on World wide web companion (WWW Companion 2014), pp. 233-234. [publisher]

Chordal editing is fixed-parameter tractable, with Dániel Marx. Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), pp. 214–225. [arXiv][publisher]

Interval deletion is fixed-parameter tractable, with Dániel Marx. Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), pp. 122–141. [arXiv][publisher]

An O*(1.84k) parameterized algorithm for the multiterminal cut problem, with Jianer Chen and Jia-Hao Fan. Proceedings of the 19th International Symposium on Fundamentals of Computation Theory (FCT 2013), LNCS vol. 8070, pp. 84–94. [pdf][publisher]

On parameterized and kernelization algorithms for the hierarchical clustering problem, with Jianer Chen. Proceedings of the 10th International Conference on Theory and Applications of Models of Computation (TAMC 2013), LNCS vol. 7876, pp. 319–330. [pdf][publisher]

Cluster editing: Kernelization based on edge cuts, with Jianer Chen. Proceedings of the 5th International Symposium on Parameterized and Exact Computation (IPEC 2010), LNCS vol. 6478, pp. 60–71. [arXiv] [publisher]

On feedback vertex set: New measure and new structures, with Jianer Chen and Yang Liu. Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010), LNCS vol. 6139, pp. 93–104. [arXiv] [publisher]

Computing with unknowns in computer algebra systems, with Gabriel Dos Reis. Proceedings of Programming Languages for Mechanized Mathematics (PLMMS), Birmingham, UK, 29 July 2008. pp. 4–17.

Manuscripts under Preparation or Submission

Recognition of subclasses of circular-arc graphs.

On fork-free t-perfect Graphs, with Shenghua Wang. [arXiv]

Modification problems toward proper (Helly) circular-arc graphs. [arXiv]

Enumerating maximal induced subgraphs, with Jianxin Wang and Hanchun Yuan. [arXiv]

Other Technical Writings

Review of flows in networks by L. R. Ford Jr. and D. R. Fulkerson. ACM SIGACT News, 44(2): 28-30 (2013) [publisher]

Last updated: November 8, 2022.