An improved FPT algorithm for the flip distance problem

Summary

Given a set of points in the Euclidean plane and two triangulations of , the flip distance between these two triangulations is the minimum number of flips required to transform one triangulation into the other. The Parameterized Flip Distance problem is to decide if the flip distance between two given triangulations is equal to a given integer k. The previous best FPT algorithm runs in time ⁎ ( ), where each step has fourteen possible choices, and the length of the action sequence is bounded by 11k. By analyzing the underlying properties of the flip sequence, each step of our algorithm has only five possible choices. Based on an auxiliary graph G, we prove that the length of the action sequence for our algorithm is bounded by . As a result, we present an FPT algorithm running in time ⁎