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 H-free 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 H-free Edge Completion problem and the H-free 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 H-free Edge Deletion is NP-complete if and only if H is a graph with at least two edges-H free Edge Completion is NP-complete if and only if H is a graph with at least two non-edges and H-free Edge Editing is NP-complete if and only if H is a graph with at least three vertices. Our result on H-free 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 NP-complete problems with a parameter k. We prove that, these NP-complete problems cannot be solved in parameterized sub exponential time, i.e., in time 2o(k)·|G|O(1), unless Exponential Time Hypothesis (ETH) fails, where ETH is a widely believed complexity theoretic assumption.

[error in script]

IITH Creators: