# String Matching in (Block) Graphs: A Full Classification by Walk Length

Preprint · Sebastian Angrick, Ben Bals, Paweł Gawrychowski, Solon P. Pissis, Yuki Yonemoto

- Archive id: arxiv:2607.28159
- Published: 2026-07-30
- DOI: https://doi.org/10.4230/lipics.esa.2026.105
- arXiv: https://arxiv.org/abs/2607.28159
- Source URL: https://arxiv.org/abs/2607.28159
- PDF: https://arxiv.org/pdf/2607.28159
- Provenance: arxiv

## Abstract

We consider directed graphs in which the nodes are labeled with strings. A walk in such a graph naturally corresponds to the concatenation of the visited nodes' labels. These graphs are widely used in bioinformatics to compactly describe large collections of highly similar genomes. Given such a graph $G=(V,E)$ and a pattern of length $m$, we seek a walk whose corresponding string has an occurrence of the pattern. We call this the SMLG problem. Amir et al. \[J. Algorithms, 2000\] showed that SMLG can be solved in $\\mathcal{O}(m\|E\| + N)$ time, where $N$ is the total length of all node labels. Equi et al. \[ACM Trans. Algorithms, 2023\] showed that this is essentially optimal (under SETH). The existing lower bound assumes that the sought walk is of length $Θ(\|V\|)$. Thus, we might be able to bypass this lower bound by restricting the walk length to $b-1$, which naturally reduces to having as input a directed graph whose set of nodes is partitioned into $b$ blocks. Then, we seek a walk in this graph that starts in the first block and ends in the last block. We call this the $b$-SMBG problem. We provide a more fine-grained classification that essentially settles the complexity of $b$-SMBG parameterized by $b$: (1) We give a near-linear-time algorithm for $b=3$. (2) We show that there is no combinatorial algorithm improving over the state-of-the-art $\\mathcal{O}(m\|E\| + N)$ bound for any $b\\ge 4$. (3) We also present a fast matrix multiplication-based algorithm yielding an improvement for $b \\in \\mathcal{O}(1)$, which is conditionally optimal. (4) Finally, we show that under SETH, for any $b \\in ω(\\log \|V\|)$, no algorithm can improve over the state of the art.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.