cs.DM
On the Parameterized Complexity Of Grid Contraction. For a family of graphs mathcal G , the mathcal G textsc 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 mathcal 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 textsc Grid Contraction from the parameterized complexity point of view. We present a fixed parameter tractable algorithm, running in time c k cdot V(G) mathcal O (1) , for this problem. We complement this result by proving that unless ETH fails, there is no algorithm for textsc Grid Contraction with running time c o(k) cdot V(G) mathcal O (1) . We also present a polynomial kernel for this problem.