A trichotomy for regular simple path queries on graphs

DOI10.1016/J.JCSS.2019.08.006MaRDI QIDQ2009646zbMATH OpenOpenAlexWikidataFDO

Authors Guillaume Bagan, Angela Bonifati, Benoît Groz

Publication date 29 November 2019

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1212.6857, https://hal.inria.fr/hal-02435355/file/jcss19%20%281%29.pdf

zbMATH Keywords

graphscomplexityautomataregular languagesregular simple paths

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: Regular path queries (RPQs) select nodes connected by some path in a graph. The edge labels of such a path have to form a word that matches a given regular expression. We investigate the evaluation of RPQs with an additional constraint that prevents multiple traversals of the same nodes. Those regular simple path queries (RSPQs) find several applications in practice, yet they quickly become intractable, even for basic languages such as (aa)* or a*ba*. In this paper, we establish a comprehensive classification of regular languages with respect to the complexity of the corresponding regular simple path query problem. More precisely, we identify the fragment that is maximal in the following sense: regular simple path queries can be evaluated in polynomial time for every regular language L that belongs to this fragment and evaluation is NP-complete for languages outside this fragment. We thus fully characterize the frontier between tractability and intractability for RSPQs, and we refine our results to show the following trichotomy: Evaluations of RSPQs is either AC0, NL-complete or NP-complete in data complexity, depending on the regular language L. The fragment identified also admits a simple characterization in terms of regular expressions. Finally, we also discuss the complexity of the following decision problem: decide, given a language L, whether finding a regular simple path for L is tractable. We consider several alternative representations of L: DFAs, NFAs or regular expressions, and prove that this problem is NL-complete for the first representation and PSPACE-complete for the other two. As a conclusion we extend our results from edge-labeled graphs to vertex-labeled graphs and vertex-edge labeled graphs.

Recommendations

• Finding Regular Simple Paths in Graph Databases
• Evaluation and enumeration problems for regular path queries
• Formal language constrained path problems
• scientific article; zbMATH DE number 2090027
• Complexity of conjunctive regular path query homomorphisms

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• A Polynomial-Time Algorithm for Finding Regular Simple Paths in Outerplanar Graphs
• Color-coding
• Complexity results on labeled shortest path problems from wireless routing metrics
• Directed tree-width
• Evaluation and enumeration problems for regular path queries
• Finding k Disjoint Paths in a Directed Planar Graph
• Finding Regular Simple Paths in Graph Databases
• Finding an Even Simple Path in a Directed Planar Graph
• Formal-Language-Constrained Path Problems
• Graph minors. XIII: The disjoint paths problem
• Modularity of cycles and paths in graphs
• Nondeterministic Space is Closed under Complementation
• On finite monoids having only trivial subgroups
• Space-bounded hierarchies and probabilistic computations
• The Theory of Definite Automata
• The complexity of regular expressions and property paths in SPARQL
• The even-path problem for graphs and digraphs

Cited in

(11)

• scientific article; zbMATH DE number 2090027 (Why is no real title available?)
• Formal languages in information extraction and graph databases
• Fine-Grained Complexity of Regular Path Queries
• Evaluation and enumeration problems for regular path queries
• Foundations of graph path query languages. Course notes for the reasoning web summer school 2021
• Finding Regular Simple Paths in Graph Databases
• Path querying on acyclic graphs using Boolean grammars
• A Trichotomy for Regular Trail Queries
• scientific article; zbMATH DE number 7650892 (Why is no real title available?)
• Digraphs of bounded width
• Formal language constrained path problems

This page was built for publication: A trichotomy for regular simple path queries on graphs

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