On the parameterized complexity of Grid Contraction

摘要

For a family of graphs G, the G-Contraction problem takes as an input a graph G and an integer k, and the goal is to decide if there exists a subset F⊆E(G) of size at most k such that G/F is in G. Here, G/F is the graph obtained from G by contracting all the edges in F. In this article, we initiate the study of Grid Contraction from the parameterized complexity point of view. We present a fixed parameter tractable algorithm, running in time 2O(k)⋅|V(G)|O(1), for this problem. We complement this result by proving that unless ETH fails, there is no algorithm for Grid Contraction with running time 2o(k)⋅|V(G)|O(1). We also present a polynomial kernel for this problem.