Next: Network Design
Up: Miscellaneous
Previous: MINIMUM TREE WIDTH
  Index
- 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.
Viggo Kann
2000-03-20