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.
