Parameterizing from the extremes: Feasible parameterizations of some NP-Optimization problems [HBNI Th22]

Abstract

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, different parameterizations of NP-optimization 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 NP-optimization problems is the standard parameterized version, where the parameter is the solution size. To start with, it is shown 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. 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 “above-guarantee” 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 above-guarantee and below-guarantee parameterization with respect to a tight bound is fixed-parameter tractable or W-hard. 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 NP-optimization problems. Then related questions in the approximation algorithms setting are considered. It investigates the possibility of obtaining an approximation algorithm for an NP-optimization problem that is an E-fraction better than the best known 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 E and the input-size, that deliver (alpha + Epsilon)-approximate solutions. It is discussed that a technique that allows to author to obtain such algorithms for a class of NP-optimization 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 Full-Degree 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 point-of-view. 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 well-known 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 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 given a family of subsets of a finite universe and a non-negative 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 fixed-parameter 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 color-coding technique, shows it to be fixed-parameter tractable. 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. The existence of such hash families of size smaller than that of the best-known S-perfect 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 non-negative 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 fixed-parameter 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 non-negative integer k, decide whether there exists a spanning out-tree of D with at least k vertices of full out-degree. 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 out-tree with at most k vertices of reduced out-degree. It is shown 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. An algorithm is given for this problem on general digraphs with run-time O(5.942k).