# Parameterized Algorithms for graph modification problems[HBNI Th110]

 dc.contributor.author Ashutosh Rai dc.date.accessioned 2017-05-16T05:47:40Z dc.date.available 2017-05-16T05:47:40Z dc.date.issued 2017-05-16T05:47:40Z dc.date.submitted 2016 dc.identifier.uri http://hdl.handle.net/123456789/397 dc.description.abstract This thesis investigates some graph modification problems from Parameterized Complexity point of view. A typical graph modification problem, for a fixed graph class Π, asks us to modify the input graph using small number of operations such that the resulting graph belongs to Π. Typical operations studied in the field are vertex and edge deletions. There are two choices of parameters for graph modification problems, one is the size of the graph we are looking for, the other is the editing distance. en_US The first part of the thesis deals with the former kind of parameterization and has results concerning many choices of the graph class Π. The first result establishes no polynomial kernelization under standard complexity theory assumptions for finding induced hereditary subgraphs for many choices of Π, including cographs, chordal, interval, split, perfect, and cluster graphs. In the other result, the class Π is the set of q-colorable graphs. We give efficient FPT algorithms for finding induced q-colorable subgraphs on graphs where either all maximal independent sets can be enumerated in polynomial time or where the maximum independent set can be found in polynomial time. The second part of the thesis deals with the more conventional parameter choice, which is the edit distance, more commonly called the solution size. We first give efficient FPT algorithms for Split Vertex Deletion and Split Edge Deletion when parameterized by the solution size. We also give polynomial kernels for both the problems. Then we consider the problem of deleting both vertices and edges to get a forest, which is a generalization of classic Feedback Vertex Set problem, and show that it is FPT. Then we propose another parameterization for graph editing problems where after deleting a small number of vertices, we want every connected component of the resulting graph to be close to a well understood graph class Π, where the measure of closeness is the minimum number of edges to be deleted from that connected component to reach the graph class. We argue how this parameterization is more powerful than the standard parameterizations for graph editing problems, and show this version to be FPT for two choices of Π, forests and bipartite graphs. While showing the latter, we also develop an algorithm for a generalization of the classic Min-Cut problem, called Mixed Cut, where we are allowed to delete both vertices and edges to disconnect the given terminals. We also show that Mixed Cut is NP–complete. dc.publisher.publisher dc.subject Parameterized Algorithms en_US dc.subject Kernelization Lower Bounds en_US dc.subject Subgraph Problems en_US dc.subject Graph Modification Problems en_US dc.subject HBNI Th110 en_US dc.title Parameterized Algorithms for graph modification problems[HBNI Th110] en_US dc.type.degree Ph.D en_US dc.type.institution HBNI en_US dc.description.advisor Saket Saurabh dc.description.pages 250p. en_US dc.type.mainsub Computer Science en_US

## Files in this item

Files Size Format View
HBNI Th110.pdf 2.148Mb PDF View/Open