Graph Modification Problems and Their Parameterized Complexity

报告人: Dr. Yinxin Cao(操宜新)  Research Assistant Professor Department of Computing，Hong Kong Polytechnic University

时间: 4月29日上午10:00——12:00

地点: 软件园校区新教师办公楼（医务室旁边）二楼会议室

主持人：朱大铭 教授

Abstract:  We are given as input a graph G, and the goal is to apply certain operations on G (such as vertex deletions, edge deletions, and/or additions) in order to obtain a graph G' with some particular property. Graphs play an important role in data modeling. They often have some specific properties, which, however, don't exhibit because of the existence of errors. Here modifications are used to detect the errors, and most graph modification problems have been formulated in this way.  Since many hard problems, including clique and coloring, become tractable on some special graphs, graph modification problems to these special graphs can be used as subroutines to solve these problems. Moreover, graph modification problems have also been associated with sparse matrix computation, and are known to be equivalent to various classic computational problems. We focus on their parameterized computation. This talk will review recent exciting progress in this direction.

Bio: Dr. Yixin Cao is a Research Assistant Professor at Department of Computing, Hong Kong Polytechnic University. Before taking the current position, he was a research fellow at Institute for Computer Science and Control, Hungarian Academy of Sciences. He has been visiting scholar in Institute for Computational and Experimental Research in Mathematics (ICERM), Brown University. His general research interests are in graph algorithms, combinatorial optimization, and their usages in social networks.

Dr. Cao received the B.E. degree in automation from Harbin Engineering University, China in 2000, the M.Sc. degree in computer science from Beihang University, China in 2003, and Ph.D. degree in computer science from Texas A&M University, USA in 2012.