Digital Repository

Parameterized Complexity of Minimum k Union Problem

Show simple item record

dc.contributor.advisor MAITY, SOUMEN en_US
dc.contributor.author KABRA, ADITYA en_US
dc.date.accessioned 2018-05-17T03:08:46Z
dc.date.available 2018-05-17T03:08:46Z
dc.date.issued 2018-05 en_US
dc.identifier.uri http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/1005
dc.description.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. en_US
dc.language.iso en en_US
dc.subject 2018
dc.subject Mathematics en_US
dc.subject Parameterized Complexity en_US
dc.subject AlgorithMS en_US
dc.title Parameterized Complexity of Minimum k Union Problem en_US
dc.type Thesis en_US
dc.type.degree BS-MS en_US
dc.contributor.department Dept. of Mathematics en_US
dc.contributor.registration 20131108 en_US


Files in this item

This item appears in the following Collection(s)

  • MS THESES [1705]
    Thesis submitted to IISER Pune in partial fulfilment of the requirements for the BS-MS Dual Degree Programme/MSc. Programme/MS-Exit Programme

Show simple item record

Search Repository


Advanced Search

Browse

My Account