2015/11/17 by Komusiewicz, Christian · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1511.05449
For a graph class Π, the Π-Vertex Deletion problem has as input an undirected graph G=(V,E) and an integer k and asks whether there is a set of at most k vertices that can be deleted from G such that the resulting graph is a member of Π. By a classic result of Lewis and Yannakakis [J. Comput. Syst. Sci. '80], Π-Vertex Deletion is NP-hard for all hereditary properties Π. We adapt the original NP-hardness construction to show that under the Exponential Time Hypothesis (ETH) tight complexity results can be obtained. We show that Π-Vertex Deletion does not admit a 2o(n)-time algorithm where n is the number of vertices in G. We also obtain a dichotomy for running time bounds that include the number m of edges in the input graph: On the one hand, if Π contains all independent sets, then there is no 2o(n+m)-time algorithm for Π-Vertex Deletion. On the other hand, if there is a fixed independent set that is not contained in Π and containment in Π can determined in 2O(n) time or 2o(m) time, then Π-Vertex Deletion can be solved in 2O(√(m))+O(n) or 2^o(m)+O(n) time, respectively. We also consider restrictions on the domain of the input graph G. For example, we obtain that Π-Vertex Deletion cannot be solved in 2o(√(n)) time if G is planar and Π is hereditary and contains and excludes infinitely many planar graphs. Finally, we provide similar results for the problem variant where the deleted vertex set has to induce a connected graph.