On the parameterized complexity of grid contraction (Q2672940)

This paper initiates the parameterized study of the grid contraction problem. The input to the \(\mathcal{G}\)-contraction problem for a family of graphs \(\mathcal{G}\) is a graph \(G\) and an integer \(k\), and the goal is to decide if there exists a subset of at most \(k\) edges whose contraction in \(G\) makes the contracted graph a member of \(\mathcal{G}\). The authors propose a parameterized algorithm with running time \(2^{\mathcal{O}(k)}|V(G)|^{\mathcal{O}(1)}\) for this problem with respect to the grid family of graphs. Moreover, they provide a kernelization algorithm for this problem. Finally, they show, under the ETH assumption, that their algorithm is optimal.