摘要：For a family of graphs ð'¢, the ð'¢-Contraction problem takes as an input a graph G and an integer k, and the goal is to decide if there exists F âS E(G) of size at most k such that G/F belongs to ð'¢. 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 c^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 c^{o(k)} â<. V(G) ^{{O}(1)}. We also present a polynomial kernel for this problem.
