Matching walks that are minimal with respect to edge inclusion
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917758842699776 |
|---|---|
| author | Marsault, Victor |
| author_facet | Marsault, Victor |
| contents | In this paper we show that enumerating the set MM(G,R), defined below, cannot be done with polynomial-delay in its input G and R, unless P=NP. R is a regular expression over an alphabet $Σ$, G is directed graph labeled over $Σ$, and MM(G,R) contains walks of G. First, consider the set Match(G,R) containing all walks G labeled by a word (over $Σ$) that conforms to $R$. In general, M(G,R) is infinite, and MM(G,R) is the finite subset of Match(G,R) of the walks that are minimal according to a well-quasi-order <. It holds w<w' if the multiset of edges appearing in w is strictly included in the multiset of edges appearing in w'. Remarkably, the set MM(G,R) contains some walks that may be computed in polynomial time. Hence, it is not the case that the preprocessing phase of any algorithm enumerating MM(G,R) must solve an NP-hard problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_14048 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Matching walks that are minimal with respect to edge inclusion Marsault, Victor Databases Computational Complexity Formal Languages and Automata Theory In this paper we show that enumerating the set MM(G,R), defined below, cannot be done with polynomial-delay in its input G and R, unless P=NP. R is a regular expression over an alphabet $Σ$, G is directed graph labeled over $Σ$, and MM(G,R) contains walks of G. First, consider the set Match(G,R) containing all walks G labeled by a word (over $Σ$) that conforms to $R$. In general, M(G,R) is infinite, and MM(G,R) is the finite subset of Match(G,R) of the walks that are minimal according to a well-quasi-order <. It holds w<w' if the multiset of edges appearing in w is strictly included in the multiset of edges appearing in w'. Remarkably, the set MM(G,R) contains some walks that may be computed in polynomial time. Hence, it is not the case that the preprocessing phase of any algorithm enumerating MM(G,R) must solve an NP-hard problem. |
| title | Matching walks that are minimal with respect to edge inclusion |
| topic | Databases Computational Complexity Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2408.14048 |