The NP-completeness of the general rainbow path problem is proved in
[1]} by a reduction from from
3-Sat. Examining the proof reveals that the instances generated by
the reduction are edge-colored graphs whose color classes are all isomorphic
either to \(K_2\)  (a single edge) or \(K_2 + K_2\) . Thus, this proof actually
provides a polynomial reduction from 3-Sat to \(\lbrace K_2, K_2 +K_2\rbrace \) -Rainbow Path.
