Consensus Strings with Small Maximum Distance and Small Distance Sum

The parameterised complexity of consensus string problems (Closest String, Closest Substring, Closest String with Outliers) is investigated in a more general setting, i. e. , with a bound on the maximum Hamming distance and a bound on the sum of Hamming distances between solution and input strings. We completely settle the parameterised complexity of these generalised variants of Closest String and Closest Substring, and partly for Closest String with Outliers; in addition, we answer some open questions from the literature regarding the classical problem variants with only one distance bound. Finally, we investigate the question of polynomial kernels and respective lower bounds.

Authors

• Laurent Bulteau
• Markus L. Schmid

Keywords

• Consensus String Problems
• Closest String
• Closest Substring
• Parameterised Complexity
• Kernelisation