Browsing by Author "Smith, Andrew, D."

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    A W[2]-Hard Variant of Common Approximate Substring
    (2002) Smith, Andrew, D.
    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.
  • Thumbnail Image
    Item
    The Parameterized Complexity of p-Center Approximate Substring Problems
    Evans, Patricia, A.; Smith, Andrew, D.; Wareham, H., T.
    Problems associated with finding strings that are within a specified Hamming distance of a given set of strings occur in several disciplines. All of the problems investigated are NP-hard and have varying levels of approximability. In this paper, we use techniques from parameterized computational complexity to assess non-polynomial time algorithmic options for three of these problems, namely p-exact substring (pes), approximate substring (1as), and p-approximate substring (pas). These problems vary whether the substring must be an exact match, and also whether a single substring or a set of substrings (of cardinality p) is required. Our analyses indicate under which parameter restrictions useful algorithms are possible, and include both class membership and parameterized reductions to prove class hardness. Since variation in parameter restrictions will lead to different algorithms being preferable, we give a variety of algorithms for the fixed parameter tractable problem variations. One of these, for 1as with alphabet, substring length, and distance all fixed, is an improvement of one of the best previously known exact algorithms (under these restrictions). Other algorithms solve parameterized variants previously unexplored. We also prove that pes is NP-hard, and show inapproximability for pes and pas.