PARAMETERIZING FROM THE EXTREMES: FEASIBLE PARAMETERIZATIONS OF SOME NP-OPTIMIZATION PROBLEMS
Somnath Sikdar · 2010
Parameterized complexity is a newly developed sub-area of computational complexity that allows for a more refined analysis of problems that are considered hard in the classical sense. In contrast to the classical theory where the complexity of a problem is measured in terms of the input size only, parameterized complexity seeks to exploit the internal structure of a problem. The complexity of a problem in this case is measured not just in terms of the input size but in terms of the input size and, what is called, the parameter. A parameterized problem is a decision problem whose instances consist of tuples (I, k), where n = |I| is the size of the input instance and k is the parameter. The goal here is to design algorithms that decide whether (I, k) is a yes-instance in time f(k) ·nO(1), where f is a computable function of k alone, as against a trivial algorithm with running time nk+O(1). Problems that admit such algorithms are said to be fixed-parameter tractable and FPT denotes the class of all fixed-parameter tractable problems. The parameter, however, is not unique and often there are several ways in which a problem can be parameterized. This is, in fact, one of the strengths of parameterized complexity as it allows the same problem to be analyzed in different ways depending on the parameter. In this thesis, we study different parameterizations of NP-optimization problems with the intent of identifying those parameterizations that are feasible and most likely to be useful in practice. A commonly studied parameterization of NP-optimization problems is the standard parameterized version, where the parameter is the solution size. We begin by showing that a number of NP-optimization problems, and in particular problems in MAX SNP, have the property that their optimum solution size is bounded below by an unbounded function of the input size. We show that the standard parameterized version of these problems is trivially in FPT and we argue that the natural parameter in such cases is the deficit between the optimum and the lower bound. That is, one ought to parameterize above the guaranteed lower bound and we call such a parameterization an “above-guarantee” parameterization. One can similarly define parameterizations below a guaranteed upper bound. We then introduce the notion of “tight” lower and upper bounds and exhibit problems for which the above-guarantee and below-guarantee parameterization with respect to a tight bound is fixed-parameter tractable or W-hard. We show that if we parameterize “sufficiently” above or below tight bounds, then these parameterized versions are not in FPT, unless P = NP, for a class of NP-optimization problems. We then consider related questions in the approximation algorithms setting. We investigate the possibility of obtaining an approximation algorithm for an NP-optimization problem that is an ǫ-fraction better than the bestknown approximation ratio for the problem. Since the best-known ratio could also be the approximation lower-bound for the problem, the algorithm in question could possibly have a worst-case exponential-time complexity. But the challenge is to obtain moderately exponential-time algorithms, whose run-time is possibly a function of ǫ and the input-size, that deliver (α + ǫ)-approximate solutions. We discuss a technique that allows us to obtain such algorithms for a class of NP-optimization problems. We next study the parameterized complexity (and occasionally the approximability) of a number of concrete problems: Kőnig Subgraph problems, Unique Coverage and its weighted variant, a version of the Induced Subgraph problem in directed graphs, and the Directed FullDegree Spanning Tree problem. The Kőnig Subgraph problem is actually a set of problems where the goal is to decide whether a given graph has a Kőnig subgraph of a certain size. A graph is Kőnig if the size of a maximum matching equals that of a minimum vertex cover in the graph. Such graphs have been studied extensively from a structural point-of-view. In this thesis, we initiate the study of the parameterized complexity and approximability of finding Kőnig subgraphs of a given graph. We will see that one of the Kőnig Subgraph problems, namely Kőnig Vertex Deletion, is closely related to a well-known problem in parameterized complexity called Above Guarantee Vertex Cover. While studying the parameterized complexity of Kőnig Vertex Deletion, we will also see some interesting structural relations between matchings and vertex covers of a graph. Unique Coverage is a natural maximization version of the well-known Set Cover problem and has applications in wireless networking and radio broadcasting. It is also a natural generalization of the well-known Max Cut problem. In this problem we are given a family of subsets of a finite universe and a nonnegative integer k as parameter, and the goal is to decide whether there exists a subfamily that covers at least k elements exactly once. We show that this problem is fixed-parameter tractable by exhibiting a problem kernel with 4k sets. We also consider a weighted variant of it called Budgeted Unique Coverage and, by an application of the color-coding technique, show it to be fixed-parameter tractable. Our application of color-coding uses an interesting variation of k-perfect hash families where for every s-element subset S of the universe, and for every k-element subset X of S, there exists a function that maps X injectively and maps the remaining elements of S into a different range. Such families are called (k, s)-hash families and were studied before in the context of coding theory. We prove, using the probabilistic method, the existence of such hash families of size smaller than that of the best-known s-perfect hash families. Explicit constructions of such hash families of size promised by the probabilistic method is open. We study a version of the Induced Subgraph problem in directed graphs defined as follows: given a hereditary property P on digraphs, an input digraph D and a nonnegative integer k, decide whether D has an induced subdigraph on k vertices with property P. We completely characterize hereditary properties for which this induced subgraph problem is W[1]-complete for two classes of directed graphs: general directed graphs and oriented graphs. We also characterize those properties for which the induced subgraph problem is W[1]-complete for general directed graphs but fixed-parameter tractable for oriented graphs. We also study a directed analog of a problem called Full Degree Spanning Tree which has applications in water distribution networks. This problem is defined as follows: given a digraph D and a nonnegative integer k, decide whether there exists a spanning out-tree of D with at least k vertices of full out-degree. We show that this problem is W[1]-hard on two important digraph classes: directed acyclic digraphs and strongly connected digraphs. In the dual version, called Reduced Degree Spanning Tree, one has to decide whether there exists a spanning out-tree with at most k vertices of reduced out-degree. We show that this problem is fixed-parameter tractable and admits a problem kernel with at most 8k vertices on strongly connected digraphs and O(k2) vertices on general digraphs. We also give an algorithm for this problem on general digraphs with run-time O∗(5.942k).