Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2402.16205 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911783995834368 |
|---|---|
| author | Cotumaccio, Nicola |
| author_facet | Cotumaccio, Nicola |
| contents | Pattern matching queries on strings can be solved in linear time by Knuth-Morris-Pratt (KMP) algorithm. In 1973, Weiner introduced the suffix tree of a string [FOCS 1973] and showed that the seemingly more difficult problem of computing matching statistics can also be solved in liner time. Pattern matching queries on graphs are inherently more difficult: under the Orthogonal Vector hypothesis, the graph pattern matching problem cannot be solved in subquadratic time [TALG 2023]. The complexity of graph pattern matching can be parameterized by the topological complexity of the considered graph, which is captured by a parameter $ p $ [JACM 2023].
In this paper, we show that, as in the string setting, computing matching statistics on graph is as difficult as solving standard pattern matching queries. To this end, we introduce a notion of longest common prefix (LCP) array for arbitrary graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_16205 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Enhanced Graph Pattern Matching Cotumaccio, Nicola Data Structures and Algorithms Pattern matching queries on strings can be solved in linear time by Knuth-Morris-Pratt (KMP) algorithm. In 1973, Weiner introduced the suffix tree of a string [FOCS 1973] and showed that the seemingly more difficult problem of computing matching statistics can also be solved in liner time. Pattern matching queries on graphs are inherently more difficult: under the Orthogonal Vector hypothesis, the graph pattern matching problem cannot be solved in subquadratic time [TALG 2023]. The complexity of graph pattern matching can be parameterized by the topological complexity of the considered graph, which is captured by a parameter $ p $ [JACM 2023]. In this paper, we show that, as in the string setting, computing matching statistics on graph is as difficult as solving standard pattern matching queries. To this end, we introduce a notion of longest common prefix (LCP) array for arbitrary graphs. |
| title | Enhanced Graph Pattern Matching |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2402.16205 |