Evaluation and enumeration problems for regular path queries
From MaRDI portal
Publication:3305367
DOI10.4230/LIPICS.ICDT.2018.19zbMATH Open1489.68081arXiv1710.02317OpenAlexW2792264844MaRDI QIDQ3305367FDOQ3305367
Publication date: 6 August 2020
Abstract: Evaluation of regular path queries (RPQs) is a central problem in graph databases. We investigate the corresponding enumeration problem, that is, given a graph and an RPQ, enumerate all paths in the graph that match the RPQ. We consider several versions of this problem, corresponding to different semantics of RPQs that have recently been considered: arbitrary paths, shortest paths, simple paths, and trails. Whereas arbitrary and shortest paths can be enumerated in polynomial delay, the situation is much more intricate for simple paths and trails. For instance, already the question if a given graph contains a simple path or trail of a certain length has cases with highly non-trivial solutions and cases that are long-standing open problems. In this setting, we study RPQ evaluation from a parameterized complexity perspective. We define a class of simple transitive expressions that is prominent in practice and for which we can prove two dichotomy-like results: one for simple paths and one for trails paths. We observe that, even though simple path semantics and trail semantics are intractable for RPQs in general, they are feasible for the vast majority of the kinds of RPQs that users use in practice. At the heart of this study is a result of independent interest on the parameterized complexity of finding disjoint paths in graphs: the two disjoint paths problem is W[1]-hard if parameterized by the length of one of the two paths.
Full work available at URL: https://arxiv.org/abs/1710.02317
Recommendations
Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Database theory (68P15) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
- The complexity of computing the permanent
- The directed subgraph homeomorphism problem
- Color-coding
- Automata, Languages and Programming
- Parameterized Algorithms
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
- Finding the K Shortest Loopless Paths in a Network
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Finding Regular Simple Paths in Graph Databases
- Title not available (Why is that?)
- Finding Two Edge-Disjoint Paths with Length Constraints
- Parameterized Approximability of the Disjoint Cycle Problem
- The even-path problem for graphs and digraphs
- Relative expressive power of navigational querying on graphs using transitive closure
- Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
- Title not available (Why is that?)
- Efficient enumeration of words in regular languages
- Querying Graphs with Data
- The complexity of regular expressions and property paths in SPARQL
- Parameterized tractability of edge-disjoint paths on directed acyclic graphs
Cited In (10)
- Fine-Grained Complexity of Regular Path Queries
- A trichotomy for regular simple path queries on graphs
- Finding Regular Simple Paths in Graph Databases
- On the Complexity of Evaluating Regular Path Queries over Linear Existential Rules
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Formal language constrained path problems
Uses Software
This page was built for publication: Evaluation and enumeration problems for regular path queries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3305367)
