Please use this identifier to cite or link to this item:
Title: Kernels for the F deletion problem
Researcher: Misra, Neeldhara
Guide(s): Venkatesh, Raman
Keywords: Kernalization
Upload Date: 17-Sep-2012
University: Homi Bhabha National Institute
Completed Date: September 2011
Abstract: In this thesis, we use the parameterized framework for the design and analysis of algorithms for NP-complete problems. This amounts to studying the parameterized version of the classical decision version. Herein, the classical language appended with a secondary measure called a ?parameter?. The central notion in parameterized complexity is that of fixed-parameter tractability, which means given an instance (x, k) of a parameterized language L, deciding whether (x, k) ! L in time f(k) ?p(|x|), where f is an arbitrary function of k alone and p is a polynomial function. The notion of kernelization formalizes preprocessing or data reduction, and refers to polynomial time algorithms that transform any given input into an equivalent instance whose size is bounded as a function of the parameter alone. The center of our attention in this thesis is the F-Deletion problem, a vastly general question that encompasses many fundamental optimization problems as special cases. In particular, we provide evidence supporting a conjecture about the kernelization complexity of the problem, and this work branches off in a number of directions, leading to results of independent interest. We also study the Colorful Motifs problem, a well-known question that arises frequently in practice. Our investigation demonstrates the hardness of the problem even when restricted to very simple graph classes. The F-Deletion Problem Let F be a finite family of graphs. The F-Deletion problem takes as input a graph G on n vertices, and a positive integer k. The question is whether it is possible to delete at most k vertices from G such that the remaining graph contains no graph from F as a minor. This question encompasses fundamental problems such as Vertex Cover (consider F consisting of the graph with two vertices and one edge) or Feedback Vertex Set (the set F consists of a cycle with three vertices). A number of other deletion-based optimization problems also turn out to be special cases of Planar F-Deletion.
Pagination: 233p.
Appears in Departments:Department of Mathematical Sciences

Files in This Item:
File Description SizeFormat 
01_title.pdfAttached File353.34 kBAdobe PDFView/Open
02_certificate.pdf25.93 kBAdobe PDFView/Open
03_declaration.pdf12.74 kBAdobe PDFView/Open
04_acknowledgements.pdf31.28 kBAdobe PDFView/Open
05_abstract.pdf86.84 kBAdobe PDFView/Open
06_contents.pdf134.12 kBAdobe PDFView/Open
07_list of figures.pdf141.73 kBAdobe PDFView/Open
08_list of tables.pdf53.06 kBAdobe PDFView/Open
09_chapter 1.pdf979.28 kBAdobe PDFView/Open
10_chapter 2.pdf219.47 kBAdobe PDFView/Open
11_chapter 3.pdf183.09 kBAdobe PDFView/Open
12_chapter 4.pdf273.02 kBAdobe PDFView/Open
13_chapter 5.pdf355.99 kBAdobe PDFView/Open
14_chapter 6.pdf406.56 kBAdobe PDFView/Open
15_chapter 7.pdf289.28 kBAdobe PDFView/Open
16_chapter 8.pdf321.04 kBAdobe PDFView/Open
17_chapter 9.pdf227.89 kBAdobe PDFView/Open
18_chapter 10.pdf325.55 kBAdobe PDFView/Open
19_chapter 11.pdf296.38 kBAdobe PDFView/Open
20_chapter 12.pdf280.09 kBAdobe PDFView/Open
21_chapter 13.pdf207.45 kBAdobe PDFView/Open
22_chapter 14.pdf286.19 kBAdobe PDFView/Open
23_chapter 15.pdf515.34 kBAdobe PDFView/Open
24_chapter 16.pdf164.56 kBAdobe PDFView/Open
25_references.pdf163.83 kBAdobe PDFView/Open
26_summary.pdf55.52 kBAdobe PDFView/Open

Items in Shodhganga are protected by copyright, with all rights reserved, unless otherwise indicated.

Altmetric Badge: