= Solution
The printed formula for the <edge> label has mismatched variable names. The type-correct reading is $x_i=\sigma(v_{i-1},v_i)$. Interpret the requested route as a <directed walk> of consecutive labelled <edges>, allowing repeated <vertices>; the distinction from a vertex-simple <directed path> is discussed below.
Let $R_t$ be the <set> of <vertices> reachable from the specified start after reading exactly the first $t$ labels. Initialize $R_0=\{v_0\}$ and update
$$
R_t=\{v:\text{there is }(u,v)\in E\text{ with }u\in R_{t-1}\text{ and }\sigma(u,v)=x_t\}.
$$
After $k$ stages, answer \b[yes exactly when $R_k\ne\varnothing$]. A <directed walk> realizing a prefix decomposes into a walk realizing the shorter prefix and one correctly labelled final <edge>; conversely every such extension is valid. This proves the <dynamic programming> invariant by <induction> on $t$. Store reachable <vertices> in Boolean <arrays> and scan the <edges> per stage. The <running time> is $O(k(|V|+|E|))$ with $O(|V|)$ rolling-table <space complexity>, in addition to <graph> storage. The empty label sequence is realized by staying at $v_0$.
If “path” is instead required to mean vertex-simple, augment the state to $(S,v)$, where $S$ is the <set> of visited <vertices>. Start with $R_0(\{v_0\},v_0)$ and extend a matching <edge> to $w$ only when $w\notin S$, replacing $S$ by $S\cup\{w\}$. This gives an exact <dynamic programming> <algorithm> for that interpretation too; reject immediately when $k\ge|V|$. A straightforward bound is $O(k2^{|V|}(|V|+|E|))$ <running time> with $O(2^{|V|}|V|)$ rolling-table storage. The exponential distinction is substantive: all labels equal and $k=|V|-1$ include the <Hamiltonian path> problem from a fixed start. The efficient layered recurrence answers the consecutive-edge interpretation without pretending to enforce distinct <vertices>.
Back to article page
