Parameterized Complexity of Minimum k Union Problem

Abstract

Parameterized Complexity offers an alternative perspective to deal with NP-hard problems. For certain problems, when some additional structure (parameter) of the problem is given, there exists efficient algorithms which give exact solutions in polynomial time in input size by separating the combinatorial explosion to the given parameter. Such problems are called Fixed Parameter Tractable and the main goal of the theory is to design such efficient algorithms. Parameterized Complexity theory helps us to determine whether there exists such efficient algorithms for a given problem and helps us to classify the problems in different classes based on their complexity with respect to the parameter. Covering problems are principal problems in complexity theory. Generally, a family of sets over some finite universe along with an integer k is provided as an input, the goal is to choose k sets from this family, such that the union of these k sets cover the whole universe. A generalization of covering problems is partial cover problems where instead of covering the whole universe, only a specified number of elements are covered with minimum number of sets. Partial Vertex Cover, Partial Dominating Set, and Partial Set Cover are some of the examples of partial cover problems. A natural variation of such partial cover problem is instead of covering maximum number of elements, the problem is to cover minimum number of elements of the universe by the union of k sets. Minimum k Union is one of such problem, where we are given a family of sets within a finite universe and an integer k and we are asked to choose k sets from this family in order to minimise the size of the union of chosen k sets. Another variation of Minimum k Union problem is Minimum Neighbourhood in Graph problem in which we are asked to select k vertices from the graph such that the size of the neighbourhood formed by these k vertices is minimum. In this thesis, we study the Minimum k Union Problem, Hall Set Problem and Minimum Neighbourhood Problem in the realms of parameterized complexity. We prove that all of these problems are W[1]-hard.