{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:19:16Z","timestamp":1778807956490,"version":"3.51.4"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>A regular path query (RPQ) is a regular expression q that returns all node\npairs (u, v) from a graph database that are connected by an arbitrary path\nlabelled with a word from L(q). The obvious algorithmic approach to\nRPQ-evaluation (called PG-approach), i.e., constructing the product graph\nbetween an NFA for q and the graph database, is appealing due to its simplicity\nand also leads to efficient algorithms. However, it is unclear whether the\nPG-approach is optimal. We address this question by thoroughly investigating\nwhich upper complexity bounds can be achieved by the PG-approach, and we\ncomplement these with conditional lower bounds (in the sense of the\nfine-grained complexity framework). A special focus is put on enumeration and\ndelay bounds, as well as the data complexity perspective. A main insight is\nthat we can achieve optimal (or near optimal) algorithms with the PG-approach,\nbut the delay for enumeration is rather high (linear in the database). We\nexplore three successful approaches towards enumeration with sub-linear delay:\nsuper-linear preprocessing, approximations of the solution sets, and restricted\nclasses of RPQs.<\/jats:p>","DOI":"10.46298\/lmcs-19(4:15)2023","type":"journal-article","created":{"date-parts":[[2023,11,27]],"date-time":"2023-11-27T09:45:15Z","timestamp":1701078315000},"source":"Crossref","is-referenced-by-count":5,"title":["Fine-Grained Complexity of Regular Path Queries"],"prefix":"10.46298","volume":"Volume 19, Issue 4","author":[{"given":"Katrin","family":"Casel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus L.","family":"Schmid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2023,11,27]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/lmcs.episciences.org\/12597\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/lmcs.episciences.org\/12597\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,27]],"date-time":"2023-11-27T09:45:17Z","timestamp":1701078317000},"score":1,"resource":{"primary":{"URL":"http:\/\/lmcs.episciences.org\/8625"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,27]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-19(4:15)2023","relation":{"has-preprint":[{"id-type":"arxiv","id":"2101.01945v4","asserted-by":"subject"},{"id-type":"arxiv","id":"2101.01945v3","asserted-by":"subject"},{"id-type":"arxiv","id":"2101.01945v2","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2101.01945","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2101.01945","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,27]]},"article-number":"8625"}}