Let us call \(\mathcal {A}\) -Compatible Path the problem of finding a
path avoiding forbidden transitions between two given vertices when the
transition graphs are all in \(\mathcal {A}\) . There is a polynomial-time
reduction from \(\mathcal {A}\) -Compatible Path to
\(\mathcal {A}\) -Rainbow Path by lec-magic. The former problem
was shown to be NP-complete when \(P_4 \in \mathcal {A}^{\mathrm {ind}}\)  or \(L_4\in \mathcal {A}^{\mathrm {ind}}\)  in [1]}.
