On the Parameterized Complexity Of Grid Contraction

08/18/2020

∙

by   Saket Saurabh, et al.

∙

0

∙

share

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 ⊆ 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)|^𝒪(1), for this problem. We complement this result by proving that unless fails, there is no algorithm for Grid Contraction with running time c^o(k)· |V(G)|^𝒪(1). We also present a polynomial kernel for this problem.