MINIMUM GRAPH INFERENCE

• INSTANCE: Class C of undirected edgecolored graphs, string x of colors.

• SOLUTION: A graph $G\in \vert C\vert$ 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$-\varepsilon$ for any $\varepsilon >0$ [373].

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