×

A trichotomy for regular simple path queries on graphs. (English) Zbl 1436.68131

Summary: We focus on the computational complexity of regular simple path queries (RSPQs). We consider the following problem \(\mathrm{RSPQ}(L)\) for a regular language \(L\): given an edge-labeled digraph \(G\) and two nodes \(x\) and \(y\), is there a simple path from \(x\) to \(y\) that forms a word belonging to \(L\)? We fully characterize the frontier between tractability and intractability for \(\mathrm{RSPQ}(L)\). More precisely, we prove \(\mathrm{RSPQ}(L)\) is either \(\mathrm{AC}^0\), NL-complete or NP-complete depending on the language \(L\). We also provide a simple characterization of the tractable fragment in terms of regular expressions. Finally, we also discuss the complexity of deciding whether a language \(L\) belongs to the fragment above. 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.

MSC:

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

References:

[1] Alon, N.; Yuster, R.; Zwick, U., Color-coding, J. ACM, 42, 4, 844-856 (1995) · Zbl 0885.68116
[2] Angles, R.; Arenas, M.; Barceló, P.; Hogan, A.; Reutter, J. L.; Vrgoc, D., Foundations of modern query languages for graph databases, ACM Comput. Surv., 50, 5, 68:1-68:40 (2017)
[3] Arenas, M.; Conca, S.; Pérez, J., Counting beyond a Yottabyte, or how SPARQL 1.1 property paths will prevent adoption of the standard, (WWW (2012)), 629-638
[4] Arkin, E. M.; Papadimitriou, C. H.; Yannakakis, M., Modularity of cycles and paths in graphs, J. ACM, 38, 2, 255-274 (1991) · Zbl 0799.68146
[5] Bagan, G.; Bonifati, A.; Groz, B., A trichotomy for regular simple path queries on graphs, (Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (2013), ACM), 261-272
[6] Barrett, C. L.; Jacob, R.; Marathe, M. V., Formal-language-constrained path problems, SIAM J. Comput., 30, 3, 809-837 (2000) · Zbl 0968.68066
[7] Bielefeldt, A.; Gonsior, J.; Krötzsch, M., Practical linked data access via SPARQL: the case of Wikidata, (Proceedings of LDOW Workshop (2018))
[8] Bonifati, A.; Martens, W.; Timm, T., An analytical study of large SPARQL query logs, VLDB J., 11, 2, 149-161 (2017)
[9] Bonifati, A.; Martens, W.; Timm, T., Navigating the maze of Wikidata query logs, (The World Wide Web Conference. The World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019 (2019)), 127-138
[10] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W. H. Freeman · Zbl 0411.68039
[11] Immerman, N., Nondeterministic space is closed under complementation, SIAM J. Comput., 17, 5, 935-938 (1988) · Zbl 0668.68056
[12] Immerman, N., Descriptive Complexity (1999), Springer · Zbl 0918.68031
[13] Jin, R.; Hong, H.; Wang, H.; Ruan, N.; Xiang, Y., Computing label-constraint reachability in graph databases, (SIGMOD Conference (2010)), 123-134
[14] Johnson, T.; Robertson, N.; Seymour, P. D.; Thomas, R., Directed tree-width, J. Comb. Theory, Ser. B, 82, 1, 138-154 (2001) · Zbl 1027.05045
[15] Koschmieder, A.; Leser, U., Regular path queries on large graphs, (SSDBM (2012)), 177-194
[16] Lapaugh, A. S.; Papadimitriou, C. H., The even-path problem for graphs and digraphs, Networks, 14, 4, 507-513 (1984) · Zbl 0552.68059
[17] Leser, U., A query language for biological networks, (ECCB/JBI (2005)), 39
[18] Losemann, K.; Martens, W., The complexity of regular expressions and property paths in SPARQL, ACM Trans. Database Syst. (TODS), 38, 4, 24 (2013) · Zbl 1321.68130
[19] Martens, W.; Trautner, T., Evaluation and enumeration problems for regular path queries, (ICDT. ICDT, LIPIcs, vol. 98 (2018), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik), 19:1-19:21 · Zbl 1489.68081
[20] Mendelzon, A. O.; Wood, P. T., Finding regular simple paths in graph databases, SIAM J. Comput., 24, 6, 1235-1258 (1995) · Zbl 0845.68033
[21] Nedev, Z. P., Finding an even simple path in a directed planar graph, SIAM J. Comput., 29, 685-695 (1999) · Zbl 0939.68088
[22] Nedev, Z. P.; Wood, P. T., A polynomial-time algorithm for finding regular simple paths in outerplanar graphs, J. Algorithms, 35, 2, 235-259 (2000) · Zbl 0999.68156
[23] Olken, F., Graph data management for molecular biology, Omics. J. Integr. Biol., 7, 1, 75-78 (2003)
[24] Papadimitriou, C. H., Computational Complexity (1994), Addison-Wesley · Zbl 0833.68049
[25] Perles, M.; Rabin, M.; Shamir, E., The theory of definite automata, IEEE Trans. Electron. Comput., EC-12, 3, 233-243 (June 1963) · Zbl 0158.01002
[26] Robertson, N.; Seymour, P. D., Graph minors XIII. The disjoint paths problem, J. Comb. Theory, Ser. B, 63, 1, 65-110 (1995) · Zbl 0823.05038
[27] Ruzzo, W. L.; Simon, J.; Tompa, M., Space-bounded hierarchies and probabilistic computations, J. Comput. Syst. Sci., 28, 2, 216-230 (1984) · Zbl 0573.68021
[28] Schrijver, A., Finding k disjoint paths in a directed planar graph, SIAM J. Comput., 23, 4, 780-788 (1994) · Zbl 0810.05061
[29] Schützenberger, M. P., On finite monoids having only trivial subgroups, Inf. Control, 8, 2, 190-194 (1965) · Zbl 0131.02001
[30] Ward, C. B.; Wiegand, N. M., Complexity results on labeled shortest path problems from wireless routing metrics, Comput. Netw., 54, 2, 208-217 (2010) · Zbl 1185.68862
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.