Speaker:

操宜新 （香港城市大学)

Time:

• 15:00-16:00 (Time in Beijing)
• May 15, 2023 (Thursday)

Venue:

电子科技大学清水河校区四号科研楼A区518

Abstract:

Given a graph $G$, the maximal induced subgraphs problem asks to enumerate all maximal induced subgraphs of $G$ that belong to a certain hereditary graph class. While its optimization version, known as the minimum vertex deletion problem in literature, has been intensively studied, enumeration algorithms were only known for a few simple graph classes, e.g., independent sets, cliques, and forests, until very recently [Conte and Uno, STOC 2019]. There is also a connected variation of this problem, where one is concerned with only those induced subgraphs that are connected. We introduce two new approaches, which enable us to develop algorithms that solve both variations for a number of important graph classes. A general technique that has been proven very powerful in enumeration algorithms is to build a solution map, i.e., a multiple digraph on all the solutions of the problem, and the key of this approach is to make the solution map strongly connected, so that a simple traversal of the solution map solves the problem. First, we introduce retaliation-free paths to certify strong connectedness of the solution map we build. Second, generalizing the idea of Cohen, Kimelfeld, and Sagiv [JCSS 2008], we introduce an apparently very restricted version of the maximal (connected) induced subgraphs problem, and show that it is equivalent to the original problem in terms of solvability in incremental polynomial time. Moreover, we give reductions between the two variations, so that it suffices to solve one of the variations for each class we study. Our work also leads to direct and simpler proofs of several important known results.

Speaker Bio:

Dr. Yixin Cao is an Associate Professor of Computing at Hong Kong Polytechnic University. He received the Ph.D. degree in computer science from Texas A&M University, USA in 2012. Before coming back to China, he was a research fellow at Institute for Computer Science and Control, Hungarian Academy of Sciences. His research interests are in algorithmic graph theory, fine-grained complexity and algorithm design, combinatorial optimization, and their usages in bioinformatics and social networks. His research is supported by the Hong Kong Research Grants Council (RGC) and the National Natural Science Foundation of China (NSFC).