aalto1 untyped-item.component.html
Conditional Lower Bounds for String Matching in Labelled Graphs
Loading...
Access rights
openAccess
CC BY
CC BY
Creative Commons license
Except where otherwised noted, this item's license is described as openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday, OpenAccess Series in Informatics ; Volume 132, Leibniz international proceedings in informatics
Abstract
The problem of String Matching in Labelled Graphs (SMLG) is one possible generalization of the classic problem of finding a string inside another of greater length. In its most general form, SMLG asks to find a match for a string into a graph, which can be directed or undirected. As for string matching, many different variations are possible. For example, the match could be exact or approximate, and the match could lie on a path or a walk. Some of these variations easily fall into the NP-hard realm, while other variants are solvable in polynomial time. For the latter ones, fine-grained complexity has been a game changer in proving quadratic conditional lower bounds, allowing to finally close the gap with those upper bounds that remained unmatched for almost two decades. If the match is allowed to be approximate, SMLG enjoys the same conditional quadratic lower bounds shown for example for edit distance (Backurs and Indyk, STOC’15). The case that really requires ad hoc conditional lower bounds is the one of finding an exact match that lies on a walk. In this work, we focus on explaining various conditional lower bounds for this version of SMLG, with the goal of giving an overall perspective that could help understand which aspects of the problem make it quadratic. We will introduce the reader to the field of fine-grained complexity and show how it can successfully provide the exact type of lower bounds needed for polynomial problems such as SMLG.
Description
Publisher Copyright: © Massimo Equi;
Other note
Citation
Equi, M 2025, Conditional Lower Bounds for String Matching in Labelled Graphs. in A Conte, A Conte, A Marino, G Rosone, J S Vitter & J S Vitter (eds), From Strings to Graphs, and Back Again : A Festschrift for Roberto Grossi's 60th Birthday., 7, OpenAccess Series in Informatics, vol. 132, Leibniz international proceedings in informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, International Symposium on Experimental Algorithms, Venice, Italy, 22/07/2025. https://doi.org/10.4230/OASIcs.Grossi.7