For a family of graphs GG, the GG-Contraction problem takes as an input a graph G and an integer k, and the goal is to decide if there exists F \subseteq E(G) of size at most k such that G/F belongs to GG. Here, G/F is the graph obtained from G by contracting all the edges in F. In this work, we initiate the study of Grid Contraction from the parameterized complexity point of view. We present a single exponential fixed parameter tractable algorithm for this problem. We complement this result by proving that unless \ETH\ fails, there is no sub-exponential FPT algorithm. We also present a polynomial kernel for this problem.
This is a joint work with Saket Saurabh and U\'everton dos Santos Souza.