Please use this identifier to cite or link to this item: http://hdl.handle.net/10603/4711
Title: The Kernelization complexity of some domination and covering problems
Researcher: Geevarghese, Philip
Guide(s): Venkatesh, Raman
Keywords: Graph Domination
Kernelization complexity
Upload Date: 17-Sep-2012
University: Homi Bhabha National Institute
Completed Date: September, 2011
Abstract: In graph domination problem the input is a graph, and the question is whether there exists a subgraph which ?dominates? the rest of the graph. For example, in the archetypal Dominating Set problem the input consists of a graph G and a positive integer k, and the question is whether there exists a set S of at most k vertices of G such that there is an edge in the graph from every vertex not in S to some vertex in S ? such a set S is called a dominating set of the graph. Other graph domination problems either put different constraints on the subgraph, or define the notion of domination differently, or both. In a graph covering problem the input is again a graph, and the question is whether there exists a subgraph whose removal from the graph results in a ?simple? graph. For example, in the classical Vertex Cover problem the input consists of a graph G and a positive integer k, and the question is whether there exists a set S of at most k vertices of G such that removing S from G leaves a graph with no edges. Other graph covering problems either put different constraints on the subgraph, or define the notion of simplicity differently, or both. We investigate the kernelization complexity of some NP-hard domination and covering problems. Very briefly, the idea is to associate a parameter ? a positive integer which may be expected to be small for large classes of inputs ? with each input instance. The problem now is to see if we can compress the instance in polynomial time to an equivalent instance whose size is a small function of the parameter, in polynomial time. Compressing the input to a small size then enables us to apply other methods on the small instance to solve the original problem in feasible time.In this Thesis we obtain various upper and lower bounds on the kernelization complexity of the following graph domination and covering problems. In each case, the parameter is the size of the solution being sought: Dominating Set, Connected Dominating Set, Pathwidth-One Vertex Deletion.
Pagination: 203p.
URI: http://hdl.handle.net/10603/4711
Appears in Departments:Department of Mathematical Sciences

Files in This Item:
File Description SizeFormat 
01_title.pdfAttached File207.69 kBAdobe PDFView/Open
02_certificate.pdf81.01 kBAdobe PDFView/Open
03_declaration.pdf75.76 kBAdobe PDFView/Open
04_dedication.pdf45.01 kBAdobe PDFView/Open
05_acknowledgements.pdf110.76 kBAdobe PDFView/Open
06_contents.pdf114.55 kBAdobe PDFView/Open
07_synopsis.pdf129.71 kBAdobe PDFView/Open
08_list of figures.pdf60.16 kBAdobe PDFView/Open
09_list of tables.pdf52.89 kBAdobe PDFView/Open
10_part 1.pdf247.1 kBAdobe PDFView/Open
11_part 2.pdf568.52 kBAdobe PDFView/Open
12_part 3.pdf519.66 kBAdobe PDFView/Open
13_part 4.pdf179.77 kBAdobe PDFView/Open
14_references.pdf163 kBAdobe PDFView/Open
15_abstract.pdf46.7 kBAdobe PDFView/Open
16_summary.pdf103.29 kBAdobe PDFView/Open


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