Some Results On Graph Contraction Problems[HBNI Th180]

Abstract

For a family of graphs F , the F -E DITING problem takes as an input a graph G and an integer k, and the objective is to decide if at most k edit operations on G can result in a graph that belongs to F . Various graph editing problems have been considered in the literature. These graph editing problems generalize many NP-Hard problems. Most of the studies regarding F -E DITING have been restricted to combination of vertex deletion, edge deletion or edge addition. Only recently, edge contraction as an edit operation has started to gain attention. The contraction of edge uv in graph G deletes vertices u and v from G, and replaces them by a new vertex, which is made adjacent to vertices that were adjacent to either u or v. In this thesis, we explore F -C ONTRACTION for various graph classes from the viewpoints of parameterized complexity, lossy kernelization and exact algorithms. We extend the known boundaries about graph contraction problems in several ways. We consider F -C ONTRACTION problems which do not have a polynomial kernels when parameterized by solution size. We compliment this negative result in two ways. Firstly, we present a polynomial kernel when parameterized by solution size and an additional parameter. In other words, we identify new graph classes for which there is a polynomial kernel. We also prove that these kernels are optimal under certain complexity conjecture. Secondly, we present a lossy kernel of polynomial size for all these problems. We present two FPT algorithms to append the list of graph classes F for which F -C ONTRACTION parameterized by solution size is FPT. We end this thesis with a non-trivial exact algorithm to determine what is the largest size of graph in a specific F to which an input graph can be contracted. To best of our knowledge, this is first such kind of algorithm in case of graph contraction problems.