Matching walks that are minimal with respect to edge inclusion
Victor Marsault · HAL (Le Centre pour la Communication Scientifique Directe) · 2024
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