Next: Network Design
Previous: MINIMUM TREE WIDTH
Class C of undirected edgecolored graphs, string x of colors.
and a simple path in G such that
the string of colors traversed in the path is equal to x.
Cardinality of the edge set of G.
- Bad News:
APX-hard and not approximable within 2
The same negative results are valid also if all graphs in C are