Mathematics

Dr. Ashutosh Rai
Charles University, Prague.

A graph editing problem asks for modifying an input graph with minimum number of operations (vertex deletion, edge deletion/addition) such that the resulting graph satisfies certain properties or belongs to some graph class. Many classical graph problems including Vertex Cover, Feedback Vertex Set, Odd Cycle Transversal, Cluster Editing, etc, can be looked at as graph editing problems. A lot of these problems turn out to be NP-hard due to a classic result of Lewis and Yannakakis.

In this talk, I will first introduce the field of parameterized complexity as a tool to deal with NP-completeness, along with a subfield of parameterized complexity called Kerneleization. Then I would give a brief overview of my work on graph editing problems, namely Split Vertex (Edge) Deletion, Almost Forest Deletion, Diamond-free Editing and Mixed-Cut. I would also describe a variant of graph editing problems that we had introduced, name Strong Graph Editing Problems, where we want to delete small number of vertices such that each connected component of the resulting graph is "close" to a well known graph class. Then I would describe the fixed parameter tractable algorithm for the case when the graph class is trees. I would conclude the talk with sketching some future research directions.