Abstract:

Parameterized complexity is a newly developed subarea 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 yesinstance 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 fixedparameter tractable and FPT denotes the class of all fixedparameter 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, different parameterizations of NPoptimization problems are studied with the intent of identifying those parameterizations that are feasible and most likely to be useful in practice. A commonly studied parameterization of NPoptimization problems is the standard parameterized version, where the parameter is the solution size. To start with, it is shown that a number of NPoptimization 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. It is also shown that the standard parameterized version of these problems is trivially in FPT and it is argued 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 such a parameterization could be called as an “aboveguarantee” parameterization. One can similarly define parameterizations below a guaranteed upper bound. Then the notion of “tight” lower and upper bounds are introduced and problems for which the aboveguarantee and belowguarantee parameterization with respect to a tight bound is fixedparameter tractable or Whard. It is shown that if one 'parameterize “sufficiently” above or below tight bounds', then these parameterized versions are not in FPT, unless P = NP, for a class of NPoptimization problems. Then related questions in the approximation algorithms setting are considered. It investigates the possibility of obtaining an approximation algorithm for an NPoptimization problem that is an Efraction better than the best known approximation ratio for the problem. Since the bestknown ratio could also be the approximation lowerbound for the problem, the algorithm in question could possibly have a worstcase exponentialtime complexity. But the challenge is to obtain moderately exponentialtime algorithms, whose runtime is possibly a function of E and the inputsize, that
deliver (alpha + Epsilon)approximate solutions. It is discussed that a technique that allows to author to obtain such algorithms for a class of NPoptimization problems.
It is studied that the parameterized complexity (and occasionally the approximability) of a number of concrete problems: Konig 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 Konig Subgraph problem is actually a set of problems where the goal is to decide whether a given graph has a Konig subgraph of a certain size. A graph is Konig 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 pointofview. In this thesis, the study of the parameterized complexity and approximability of finding Konig subgraphs of a given graph is initiated. It is seen that one of the Konig Subgraph problems, namely Konig Vertex Deletion, is closely related to a wellknown problem in parameterized complexity called Above Guarantee Vertex Cover. While studying the parameterized complexity of Konig Vertex Deletion, it is also observed some interesting structural relations between matchings and vertex covers of a graph. Unique Coverage is a natural maximization version of the wellknown Set Cover problem and has applications in wireless networking and radio broadcasting. It is also a natural generalization of the wellknown Max Cut problem. In this problem 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. It shows that this problem is fixedparameter tractable by exhibiting a problem kernel with 4k sets. A weighted variant of it called Budgeted Unique Coverage is also considered and, by an application of the colorcoding technique, shows it to be fixedparameter tractable. Application of colorcoding uses an interesting variation of kperfect
hash families where for every selement subset S of the universe, and for every kelement 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. The existence of such hash families of size smaller than that of the bestknown Sperfect hash families, is proved using the Probabilistic method. Explicit constructions of such hash families of size promised by the probabilistic method is open.
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 sub digraph on k vertices with property P. Hereditary properties are completely characterized for which this induced sub graph problem is W[1]complete for two classes of directed graphs: general directed graphs and oriented graphs. Also those properties for which the induced subgraph problem is W[1]complete are characterized for general directed graphs but fixedparameter tractable for oriented graphs.
A directed analog of a problem called Full Degree Spanning Tree is studied 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 outtree of D with at least k
vertices of full outdegree. It is shown 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 outtree with at most k vertices of reduced outdegree. It is shown that this problem is fixedparameter tractable and admits a problem kernel with at most 8k vertices on strongly connected digraphs and O(k2) vertices on general digraphs. An algorithm is given for this problem on general digraphs with runtime O(5.942k). 