- INSTANCE:
Class
*C*of undirected edgecolored graphs, string*x*of colors. - SOLUTION:
A graph
and a simple path in
*G*such that the string of colors traversed in the path is equal to*x*. - MEASURE:
Cardinality of the edge set of
*G*.

*Bad News:*APX-hard and not approximable within 2 for any [373].*Comment:*The same negative results are valid also if all graphs in*C*are caterpillars.