Parameterized Algorithms for Consensus String Problems

Consensus String Problems aim at combining information from different input strings into a single median “consensus” string. Several variants of the problem have been considered in the past, where one aims at minimizing either the maximum distance (“radius”) or the sum of distances (“sum”) between the consensus and the input strings. In some cases, one may also trim the ends of input strings, or even declare a few of them as “outliers”, whose distance can be ignored. Even though the problem is hard, depending on the dimensions, many special cases (parameterizations) become tractable using FPT algorithms. In this study we explore the parameterized complexity of the problem where both sum and radius constraints are given, giving more flexibility for an optimal solution. We also introduce the variant where one considers circular strings, that can be rotated to find a better consensus.