IISER Pune
INDIAN INSTITUTE OF SCIENCE EDUCATION AND RESEARCH (IISER) PUNE
where tomorrow’s science begins today
An Autonomous Institution, Ministry of Human Resource Development, Govt. of India
Links
Seminars and Colloquia

Mathematics

Graph Editing Problems: Through the Parameterized Lens 
 
Tue, Feb 11, 2020,   02:00 PM to 03:00 PM at Madhava Hall

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.

homecolloquia_seminars