= Solution
Use the multiplicative score exactly as defined in the paper. Let $P_t(v)$ be the largest score of a matching length-$t$ route ending at $v$. Initialize $P_0(v_0)=1$ and mark all other entries unreachable. For each stage, clear the new layer and inspect matching <edges> from reachable entries:
$$
P_t(v)=\max_{\substack{(u,v)\in E,\ \sigma(u,v)=x_t\\u\text{ reachable at stage }t-1}} P_{t-1}(u)\,p(u,v).
$$
An empty candidate <set> is marked unreachable, rather than given score zero: a genuine route may have score zero. A Boolean reachability table or a sentinel $-1$ with a guard before multiplication distinguishes the cases. Store the maximizing predecessor <edge> at each reachable layer entry, retaining one on a tie.
Multiplication by a nonnegative <edge> factor preserves order, so replacing a prefix by a larger-scoring matching prefix cannot worsen its extension. <Induction> proves this <maximum-product edge-labelled walk> recurrence correct. Choose a reachable final entry of greatest score and follow its layer-indexed predecessors backwards to reconstruct the answer. If no final entry is reachable, report that no matching route exists, even though all numeric scores might otherwise look like zero.
The <running time> is $O(k(|V|+|E|))$, and rolling scores have <space complexity> $O(|V|)$, while retaining all reconstruction pointers gives <space complexity> $O(k|V|)$. For the vertex-simple interpretation, retain the visited <set> in each state as in part i, prohibit revisits and maximize the same products over those states. This exact exponential-state variant preserves both the zero-score distinction and predecessor reconstruction. If the starting <vertex> is unrestricted rather than inherited from part i, initialize $P_0(v)=1$ for every <vertex>. The calculation needs no independence assumption beyond the paper's definition of a product score; repeated physical edge-activation events would require a separate probabilistic model.
Back to article page
