Computer Science – Data Structures and Algorithms
Scientific paper
2008-02-12
Computer Science
Data Structures and Algorithms
20 page, 1 Figure
Scientific paper
Covering problems are fundamental classical problems in optimization, computer science and complexity theory. Typically an input to these problems is a family of sets over a finite universe and the goal is to cover the elements of the universe with as few sets of the family as possible. The variations of covering problems include well known problems like Set Cover, Vertex Cover, Dominating Set and Facility Location to name a few. Recently there has been a lot of study on partial covering problems, a natural generalization of covering problems. Here, the goal is not to cover all the elements but to cover the specified number of elements with the minimum number of sets. In this paper we study partial covering problems in graphs in the realm of parameterized complexity. Classical (non-partial) version of all these problems have been intensively studied in planar graphs and in graphs excluding a fixed graph $H$ as a minor. However, the techniques developed for parameterized version of non-partial covering problems cannot be applied directly to their partial counterparts. The approach we use, to show that various partial covering problems are fixed parameter tractable on planar graphs, graphs of bounded local treewidth and graph excluding some graph as a minor, is quite different from previously known techniques. The main idea behind our approach is the concept of implicit branching. We find implicit branching technique to be interesting on its own and believe that it can be used for some other problems.
Amini Omid
Fomin Fedor V.
Saurabh Saket
No associations
LandOfFree
Parameterized Algorithms for Partial Cover Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Parameterized Algorithms for Partial Cover Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parameterized Algorithms for Partial Cover Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-675996