The Parameterized Complexity of p-Center Approximate Substring Problems
Loading...
Files
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.