Complexity issues of string to graph approximate matching

DOI10.1007/978-3-030-40608-0_17MaRDI QIDQ782580zbMATH OpenOpenAlexFDO

Authors Riccardo Dondi, Giancarlo Mauri, Italo Zoppis

Publication date 27 July 2020

Full work available at URL https://arxiv.org/abs/2001.01961

zbMATH Keywords

computational complexityparameterized complexitypatternsalgorithms on stringsgraph querystring-to-graph matching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: The problem of matching a query string to a directed graph, whose vertices are labeled by strings, has application in different fields, from data mining to computational biology. Several variants of the problem have been considered, depending on the fact that the match is exact or approximate and, in this latter case, which edit operations are considered and where are allowed. In this paper we present results on the complexity of the approximate matching problem, where edit operations are symbol substitutions and are allowed only on the graph labels or both on the graph labels and the query string. We introduce a variant of the problem that asks whether there exists a path in a graph that represents a query string with any number of edit operations and we show that is is NP-complete, even when labels have length one and in the case the alphabet is binary. Moreover, when it is parameterized by the length of the input string and graph labels have length one, we show that the problem is fixed-parameter tractable and it is unlikely to admit a polynomial kernel. The NP-completeness of this problem leads to the inapproximability (within any factor) of the approximate matching when edit operations are allowed only on the graph labels. Moreover, we show that the variants of approximate string matching to graph we consider are not fixed-parameter tractable, when the parameter is the number of edit operations, even for graphs that have distance one from a DAG. The reduction for this latter result allows us to prove the inapproximability of the variant where edit operations can be applied both on the query string and on graph labels.

Recommendations

• On the complexity of approximately matching a string to a directed graph
• The complexity of approximate pattern matching on de Bruijn graphs
• A graph-theoretic model to solve the approximate string matching problem allowing for translocations
• Algorithms for approximate graph matching
• Approximate string matching with suffix automata

Cited in

(4)

• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• On the Complexity of String Matching for Graphs
• The complexity of approximate pattern matching on de Bruijn graphs
• On the complexity of approximately matching a string to a directed graph

This page was built for publication: Complexity issues of string to graph approximate matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q782580)