Multivariate Algorithmic Analysis of Hitting Small Sets

When a problem has been shown to be NP-complete, often one has to be content with either exponential-time algorithms or resort to approximation algorithms that sacrifice the optimality of the solution, or with ad hoc heuristics, which often remain unreliable. In multivariate algorithms, one tries to capture any hidden structure in the input via a set of parameters. For example, for a single parameter encoded by a number k, one tries to find an algorithm whose running time is of the form f(k) · nO(1). Such an algorithm is called an FPT algorithm. The interesting property of an FPT algorithm is that if k is a fixed constant, or even grows slowly enough with the input size, the algorithm takes polynomial-time asymptotically, regardless of whether the problem is NP-complete or not. In a few decades, it has been shown that a vast number of NP-complete problems admit such algorithms. For example, consider the NP-complete problem called the Vertex Cover problem in which, given a graph on n vertices, the task is to find a set (called vertex cover) of vertices of smallest cardinality whose removal makes the graph edgeless. With the size k of the solution as the parameter, the Vertex Cover problem can be solved in O(1.2738k + k · n) time [CKX10]. So, if k is very small compared to n, the Vertex Cover problem can be solved in time linear in the size of the input! Similarly, consider the undirected Feedback Vertex Set problem in which, given an undirected graph, the task is to find a set (called feedback vertex set) of vertices of smallest cardinality whose removal makes the graph acyclic. With the size k of the solution as the parameter, this problem can be solved in O(3.592knO(1)) time [KP14] and the directed version can be solved in time O(4kkO(1)k!nm) [CLL+08]. Although different problems come with their own structure and specialized techniques are needed to solve them, there are some generic upper bounding techniques for the running time of FPT algorithms, namely branching, iterative compression and kernelization which we will encounter many times in the thesis. Furthermore, there are techniques that can be used to classify problems as those that probably do not admit FPT algorithms and to lower bound the dependence of the running time on the parameter. These techniques can only be used to show conditional results, because unconditional superpolynomial running time lower bounds for problems in NP would resolve P vs NP problem. The assumption typically used for ruling out FPT algorithms is that FPT = W[1], while the assumption used for lower bounding dependencies on k is called the Exponentialtime hypothesis(ETH). In this thesis, we make a contribution towards multivariate analysis of a class of problems known as Hitting Set problems. In a Hitting Set problem, the input consists of a universe U and a family of sets H and the task is to find a set H ⊆ U such that H contains at least one element of every set in H. Some of the most studied problems that have a natural formulation as a Hitting Set problem are Vertex Cover, Feedback Vertex Set and Dominating Set. In particular, this thesis focuses on the following problems: • Feedback Vertex Set for Tournaments, where a tournament is an orientation of a complete graph. • Feedback Vertex Set for Bipartite Tournaments, where a bipartite tournament is an orientation of a complete bipartite graph. • -Component Order Connectivity. In this problem, the input is a graph G with integers and k and the task is to determine whether there exists a set S of vertices of cardinality at most k such that in G−S (graph obtained after deleting vertices from S) the size of components (number of vertices in a connected set) is bounded by . This problem happens to be a generalization of the Vertex Cover. • Connected Dominating Set in sparse graphs. In the Dominating Set problem, the input is a graph G with an integer k and the task is to determine whether there exists a set S of vertices of cardinality at most k such that every vertex in G has at least one neighbor in S. In the Connected Dominating Set problem, we require that the induced subgraph G[S] is connected. In sparse graphs, we consider the problem on graphs of bounded degeneracy and bounded expansion. These graph classes are defined in Chapter 8. For the first two problems, we provide a unified novel approach to obtain a fast FPT and exact-exponential-time algorithm with running times 1.6181k · nO(1) and 1.3821n, respectively. In the process, we obtain structural results that may be of independent interest. The third problem is a generalization of the Vertex Cover problem and we provide a kernel of size 2 k which matches the lower bound size for = 1, which is the Vertex Cover problem itself. In this work we obtain a weighted Expansion Lemma which may be of independent interest. At the same time, we provide first non-trivial application (after the Namhauser-Trotter Theorem-based kernel for Vertex Cover) of Linear Programming based kernel. Finally, in the fourth problem, we use a new framework for obtaining polynomial kernels called Lossy Kernelization for Connected Dominating Set in graphs of bounded degeneracy and bounded expansion. For both of these problems, under reasonable complexity theoretic assumptions, a polynomial kernel is forbidden