Parameterized Algorithms for graph modification problems[HBNI Th110]

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. 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.