Next: Network Design Up: Miscellaneous Previous: MINIMUM TREE WIDTH Index

### MINIMUM GRAPH INFERENCE

- 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 [353].

- Comment: The same negative results are valid also if all graphs in C are caterpillars.