Chandrasekhar Hall

Parameterized Algorithms for Graph Modification Problems

Ashutosh Rai

IMSc

In a typical graph modification problems we are given an undirected graph $G$, a positive integers $k$ and the objective is to modify the graph by $k$-operations such that the graph satisfies some interesting properties. These operations include edge deletion, vertex deletion and edge insertion. In this thesis we look at modifying an input graph into ``other graphs'' such as split graphs, forests, and bipartite graphs. Towards that we build a new toolkit and resolve several interesting problems in the area. Finally, we also propose a stronger framework for studying graph modification problems.
(Thesis Defense)