Smith, Andrew, D.2023-03-012023-03-012002https://unbscholar.lib.unb.ca/handle/1882/14708Given 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.http://purl.org/coar/access_right/c_abf2technical reportComputer Science