A W[2]-Hard Variant of Common Approximate Substring
Loading...
Files
Date
2002
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Given a set F of strings and two integers d < l, the common approximate substring problem asks whether there is a string C of length l, such that each member of F contains a substring that differs from C in at most d positions. For a fixed number of strings, and fixed alphabet size, Fellows et al. [2] showed this problem to be hard for the class W[1] of the W-hierarchy. We strengthen this result and show that the problem is W[2]-hard by a parameterized reduction from set cover.