A W-Hard Variant of Common Approximate Substring
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.  showed this problem to be hard for the class W of the W-hierarchy. We strengthen this result and show that the problem is W-hard by a parameterized reduction from set cover.