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.
Dondi, R., Mauri, G., & Zoppis, I. (2021). On the complexity of approximately matching a string to a directed graph. INFORMATION AND COMPUTATION [10.1016/j.ic.2021.104748].
Citazione: | Dondi, R., Mauri, G., & Zoppis, I. (2021). On the complexity of approximately matching a string to a directed graph. INFORMATION AND COMPUTATION [10.1016/j.ic.2021.104748]. | |
Tipo: | Articolo in rivista - Articolo scientifico | |
Carattere della pubblicazione: | Scientifica | |
Presenza di un coautore afferente ad Istituzioni straniere: | No | |
Titolo: | On the complexity of approximately matching a string to a directed graph | |
Autori: | Dondi, R; Mauri, G; Zoppis, I | |
Autori: | ZOPPIS, ITALO FRANCESCO (Corresponding) | |
Data di pubblicazione: | 2021 | |
Lingua: | English | |
Rivista: | INFORMATION AND COMPUTATION | |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/j.ic.2021.104748 | |
Appare nelle tipologie: | 01 - Articolo su rivista |