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.

(2022). On the complexity of approximately matching a string to a directed graph [journal article - articolo]. In INFORMATION AND COMPUTATION. Retrieved from https://hdl.handle.net/10446/234193

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

Dondi, Riccardo;
2022-01-01

Abstract

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.
articolo
Dondi, Riccardo; Mauri, Giancarlo; Zoppis, Italo
(2022). On the complexity of approximately matching a string to a directed graph [journal article - articolo]. In INFORMATION AND COMPUTATION. Retrieved from https://hdl.handle.net/10446/234193
File allegato/i alla scheda:
File Dimensione del file Formato  
InformationComputation2022.pdf

Solo gestori di archivio

Versione: publisher's version - versione editoriale
Licenza: Licenza default Aisberg
Dimensione del file 745.22 kB
Formato Adobe PDF
745.22 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/234193
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact