An FPT algorithm for orthogonal buttons and scissors

07/24/2019

∙

by   Dekel Tsur, et al.

∙

0

∙

share

We study the puzzle game Buttons and Scissors in which the goal is to remove all buttons from an n× 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 k) (n+m)^O(1), where k is an upper bound on the number of cuts.