Parameterized Algorithms for Consensus String Problems

lundi 10 Décembre, 14h, salle D 102

Laurent Bulteau (LIGM, Marne-la-Vallée, France)

 

Abstract :

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.

The talk is based on joint works.
Preprint and article are available on :
https://doi.org/10.4230/LIPIcs.MFCS.2018.1
https://arxiv.org/abs/1804.02854