Results on Hardness of Edge Modification Problems and Chromatic Discrepancy of Graphs
R B, Sandeep (2016) Results on Hardness of Edge Modification Problems and Chromatic Discrepancy of Graphs. PhD thesis, Indian Institute of Technology Hyderabad.
Text
CS12P0001.pdf  Submitted Version Restricted to Registered users only until 1 July 2021. Download (896kB)  Request a copy 
Abstract
This thesis comprises two parts. In the first part, we study classical, parameterized and kernelization complexities of edge modification problems. In the second part, we introduce and study a new graph parameter named as chromatic discrepancy, which has relations to optimal coloring, local chromatic number and perfect coloring of graphs. For a graph H, the Hfree Edge Deletion problem is to check whether there exist at most k edges whose deletion from the input graph results in a graph without any induced copy of H. The Hfree Edge Completion problem and the Hfree Edge Editing problem are defined similarly where only completion (addition) of edges are allowed in the former and both completion and deletion are allowed in the latter. Though studied for the last four decades, a complete classical complexity classification of these problems has not been known. We settle this by proving that Hfree Edge Deletion is NPcomplete if and only if H is a graph with at least two edgesH free Edge Completion is NPcomplete if and only if H is a graph with at least two nonedges and Hfree Edge Editing is NPcomplete if and only if H is a graph with at least three vertices. Our result on Hfree Edge Editing resolves a conjecture by Alon and Stav (Theoretical Computer Science, 2009). Parameterized complexity is a refinement over classical complexity. The idea is to explore the complexity of a problem based on an additional input known as the parameter. We study the parameterized complexity of these NPcomplete problems with a parameter k. We prove that, these NPcomplete problems cannot be solved in parameterized sub exponential time, i.e., in time 2o(k)·GO(1), unless Exponential Time Hypothesis (ETH) fails, where ETH is a widely believed complexity theoretic assumption.
[error in script]IITH Creators: 



Item Type:  Thesis (PhD)  
Uncontrolled Keywords:  Graph Theory, Edge Modification Problems, TD584  
Subjects:  Computer science > Big Data Analytics  
Divisions:  Department of Computer Science & Engineering  
Depositing User:  Library Staff  
Date Deposited:  12 Jul 2016 04:43  
Last Modified:  12 Jul 2016 04:43  
URI:  http://raiith.iith.ac.in/id/eprint/2518  
Publisher URL:  
Related URLs: 
Actions (login required)
View Item 
Statistics for this ePrint Item 