Matching walks that are minimal with respect to edge inclusion

Victor Marsault

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 alp…