FPT Algorithms with Polynomial Memory for the Convex String Recoloring Problem

Abstract

The Convex String Recoloring (CSR) problem measures the Hamming distance between a string of colored vertices to a convex string. This is a special case of the Convex Tree Recoloring (CTR) problem, which measures the Hamming distance to a perfect phylogeny, which was popularized by Moran and Snir. It has been shown that even if the input graphs are restricted to strings, the problem is still NP-complete. In 2008 Bar-Yehuda et al. came up with a dynamic programming approach the can solve the CSR in O^*(2^k) using exponential space. In this paper, it is shown that the CSR problem can be solved in O^*(2^k) time using only polynomial space.