{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T22:21:50Z","timestamp":1782944510518,"version":"3.54.5"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,4,12]],"date-time":"2023-04-12T00:00:00Z","timestamp":1681257600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"crossref","award":["309048, 322595, 328877"],"award-info":[{"award-number":["309048, 322595, 328877"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Research Council"},{"name":"European Union\u2019s Horizon 2020 research and innovation programme","award":["851093"],"award-info":[{"award-number":["851093"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,7,31]]},"abstract":"<jats:p>\n            Exact string matching in labeled graphs is the problem of searching paths of a graph\n            <jats:italic>G=(V, E)<\/jats:italic>\n            such that the concatenation of their node labels is equal to a given pattern string\n            <jats:italic>P<\/jats:italic>\n            [1.\n            <jats:italic>m<\/jats:italic>\n            ]. This basic problem can be found at the heart of more complex operations on variation graphs in computational biology, of query operations in graph databases, and of analysis operations in heterogeneous networks.\n          <\/jats:p>\n          <jats:p>\n            We prove a conditional lower bound stating that, for any constant \u03b5 &gt; 0, an\n            <jats:italic>O<\/jats:italic>\n            (|\n            <jats:italic>E<\/jats:italic>\n            |\n            <jats:sup>1 - \u03b5<\/jats:sup>\n            <jats:italic>m<\/jats:italic>\n            ) time, or an\n            <jats:italic>O<\/jats:italic>\n            (|\n            <jats:italic>E<\/jats:italic>\n            |\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>1 - \u03b5<\/jats:sup>\n            )time algorithm for exact string matching in graphs, with node labels and pattern drawn from a binary alphabet, cannot be achieved unless the Strong Exponential Time Hypothesis (\n            <jats:sans-serif>SETH<\/jats:sans-serif>\n            ) is false. This holds even if restricted to undirected graphs with maximum node degree 2\u2014that is, to\n            <jats:italic>zig-zag matching in bidirectional strings<\/jats:italic>\n            , or to\n            <jats:italic>deterministic<\/jats:italic>\n            directed acyclic graphs whose nodes have maximum sum of indegree and outdegree 3. These restricted cases make the lower bound stricter than what can be directly derived from related bounds on regular expression matching (Backurs and Indyk, FOCS\u201916). In fact, our bounds are tight in the sense that lowering the degree or the alphabet size yields linear time solvable problems.\n          <\/jats:p>\n          <jats:p>\n            An interesting corollary is that exact and approximate matching are equally hard (i.e.,\u00a0quadratic time) in graphs under\n            <jats:sans-serif>SETH<\/jats:sans-serif>\n            . In comparison, the same problems restricted to strings have linear time vs quadratic time solutions, respectively (approximate pattern matching having also a matching\n            <jats:sans-serif>SETH<\/jats:sans-serif>\n            lower bound (Backurs and Indyk, STOC\u201915)).\n          <\/jats:p>\n          <jats:p\/>","DOI":"10.1145\/3588334","type":"journal-article","created":{"date-parts":[[2023,3,16]],"date-time":"2023-03-16T12:12:18Z","timestamp":1678968738000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["On the Complexity of String Matching for Graphs"],"prefix":"10.1145","volume":"19","author":[{"given":"Massimo","family":"Equi","sequence":"first","affiliation":[{"name":"University of Helsinki, Helsinki, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Veli","family":"M\u00e4kinen","sequence":"additional","affiliation":[{"name":"University of Helsinki, Helsinki, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexandru I.","family":"Tomescu","sequence":"additional","affiliation":[{"name":"University of Helsinki, Helsinki, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roberto","family":"Grossi","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di, Pisa, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,4,12]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.14"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0029792"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.55"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.WABI.2018.21"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-63307-3_56"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1063"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1322432.1322433"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746612"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.56"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1053128"},{"key":"e_1_3_2_12_2","unstructured":"Arturs Backurs and Christos Tzamos. 2017. Improving Viterbi is hard: Better runtimes imply faster clique algorithms. In Proceedings of the 34th International Conference on Maching Learning (ICML\u201917) . Proceedings of Machine Learning Research Vol. 70. 311\u2013321. http:\/\/proceedings.mlr.press\/v70\/backurs17a.html."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.21"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.15"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2212.07870"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1093\/bib\/bbw089"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220085"},{"key":"e_1_3_2_18_2","first-page":"272","volume-title":"Proceedings of the Data Compression Conference (DCC\u201922)","author":"Cotumaccio Nicola","year":"2022","unstructured":"Nicola Cotumaccio. 2022. Graphs can be succinctly indexed for pattern matching in \\(O(|E|^{2} + |V|^{5\/2})\\) time. In Proceedings of the Data Compression Conference (DCC\u201922). IEEE, Los Alamitos, CA, 272\u2013281."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.153"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-20643-6_22"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2021.104748"},{"key":"e_1_3_2_22_2","article-title":"On the complexity of exact pattern matching in graphs: Binary strings and bounded degree","author":"Equi Massimo","year":"2019","unstructured":"Massimo Equi, Roberto Grossi, and Veli M\u00e4kinen. 2019. On the complexity of exact pattern matching in graphs: Binary strings and bounded degree. arXiv e-prints, arXiv:1901.05264 [cs.CC] (2019).","journal-title":"arXiv e-prints, arXiv:1901.05264 [cs.CC]"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.55"},{"key":"e_1_3_2_24_2","article-title":"On the complexity of exact pattern matching in graphs: Determinism and zig-zag matching","author":"Equi Massimo","year":"2019","unstructured":"Massimo Equi, Roberto Grossi, Alexandru I. Tomescu, and Veli M\u00e4kinen. 2019. On the complexity of exact pattern matching in graphs: Determinism and zig-zag matching. arXiv e-prints, arXiv:1902.03560 [cs.CC] (2019).","journal-title":"arXiv e-prints"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-67731-2_44"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-022-01007-w"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190657"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.06.016"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1038\/nbt.4227 10.1038\/nbt.4227"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-59212-7_6"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976496.26"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2019.51"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2022.0411"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.30"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17083-7_6"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-016-1103-9"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1142\/9789812797919_0002"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00333-3"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60044-2_51"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2020.105993"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.3390\/a14010014"},{"key":"e_1_3_2_44_2","article-title":"SPARQL Query Language for RDF","author":"Prud\u2019hommeaux Eric","year":"2008","unstructured":"Eric Prud\u2019hommeaux and Andy Seaborne. 2008. SPARQL Query Language for RDF. World Wide Web Consortium Recommendation REC-rdf-sparql-query-20080115. W3C.","journal-title":"World Wide Web Consortium Recommendation REC-rdf-sparql-query-20080115"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1147\/rd.32.0114"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1101\/216127"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/2815072.2815073"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1186\/gb-2009-10-9-r98"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2598561"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2013.2297101"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2012.10.001"},{"key":"e_1_3_2_52_2","volume-title":"On the Complexity of Intersection Non-Emptiness Problems","author":"Wehar Michael","year":"2016","unstructured":"Michael Wehar. 2016. On the Complexity of Intersection Non-Emptiness Problems. Ph.D. Dissertation. University at Buffalo, State University of New York. http:\/\/www.michaelwehar.com\/documents\/mwehar_dissertation.pdf."},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588334","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588334","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:51:28Z","timestamp":1750182688000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588334"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,12]]},"references-count":53,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,7,31]]}},"alternative-id":["10.1145\/3588334"],"URL":"https:\/\/doi.org\/10.1145\/3588334","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,12]]},"assertion":[{"value":"2020-03-10","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-07","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}