Vertex Deletion Problems

Abstract

In this thesis we study various vertex deletion problems. In a vertex deletion problem, we are given a graph G and an integer k, and want to delete at most k vertices from G such that the resulting graph belongs to a certain graph class C. We study several generalizations of the Directed Feedback Vertex Set and for each of them we either present a fixed-parameter algorithm or a hardness result. <br /> Our first result is a fixed-parameter algorithm for Directed Long Cycle Hitting Set. In this problem the graph class C is the class of all graphs with no cycle of length greater than l. We give a fixed-parameter algorithm for the parameter k + l. To achieve this we present a new generalization of important separators, as well as a new result on k-representative sets of paths. Moreover, we give fixed-parameter algorithms for Bounded Size Strongly Connected Component Vertex Deletion and 1-Out-Regular Vertex Deletion. Eventually, we consider the Negative Directed Feedback Arc Set problem, which is related to the Minimum Feasibility Blocker problem from the area of linear programming. We give hardness results and fixed-parameter algorithms for various choices of parameters.