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

2017/02/27 by Bulteau, Laurent
#Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1702.08238

Abstract

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 prove that this problem is W[1]-hard when parameterized by the maximum length of input strings.

Related

• Tight Hardness Results for Consensus Problems on Circular Strings and Time Series
• Pattern Matching and Consensus Problems on Weighted Sequences and\n Profiles
• String Consensus Problems with Swaps and Substitutions
• Separating Sets of Strings by Finding Matching Patterns is Almost Always Hard
• On the String Consensus Problem and the Manhattan Sequence Consensus\n Problem