Publication Date:
2019
Description:
〈h3〉Abstract〈/h3〉
〈p〉The parameterised complexity of various consensus string problems (〈span〉Closest String〈/span〉, 〈span〉Closest Substring〈/span〉, 〈span〉Closest String with Outliers〈/span〉) is investigated in a more general setting, i. e., with a bound on the maximum Hamming distance 〈em〉and〈/em〉 a bound on the sum of Hamming distances between solution and input strings. We completely settle the parameterised complexity of these generalised variants of 〈span〉Closest String〈/span〉 and 〈span〉Closest Substring〈/span〉, and partly for 〈span〉Closest String with Outliers〈/span〉; 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.〈/p〉
Print ISSN:
0178-4617
Electronic ISSN:
1432-0541
Topics:
Computer Science
,
Mathematics
