Consensus Patterns parameterized by input string length is W[1]-hard

Laurent Bulteau

We consider the Consensus Patterns problem, where, given a set of input strings, one is asked to extract a long-enough pattern which appears (with some errors) in all strings. We p…