An FPT algorithm for orthogonal buttons and scissors

Abstract

We study the puzzle game Buttons and Scissors in which the goal is to remove all buttons from an $n\times m$ grid by a series of horizontal and vertical cuts. We show that the corresponding parameterized problem has an algorithm with time complexity $2^{O(k^2\log k)}(n+m{)}^{O(1)}$, where $k$ is an upper bound on the number of cuts.