On the complexity of approximately matching a string to a directed graph

The problem of matching a query string to a directed graph, whose vertices are labeled by strings, has application in different fields. In this paper we present results on the complexity of the approximate matching problem, where edit operations are symbol substitutions and are allowed only to the graph labels or both to the graph labels and the query string. We show that deciding if there exists a path in a graph that represents a query string with edit operations to vertex labels is an NP-complete problem and it is fixed-parameter tractable when parameterized by the length of the input string. We show that the variants of approximate string matching we consider are not fixed-parameter tractable, when the parameter is (1) the length of the query string and (2) the number of edit operations. Moreover, we provide inapproximability results for these variants of the of approximate string matching problem. (C) 2021 Elsevier Inc. All rights reserved.

Automated summary

This paper investigates the problem of matching a query string to a directed graph, with edit operations allowed on both the graph labels and the query string. The complexity of approximate matching problem is analyzed, showing that deciding the existence of a path in the graph representing a query string with edit operations on vertex labels is an NP-complete problem. The fixed-parameter tractability of this problem is also discussed when parameterized by the length of the input string. The paper further explores the variants of approximate string matching and provides inapproximability results.