# Finding good induced subgraph

You are given a graph $G = (V,E)$ with $n$ vertices. It might be bipartite if you want. There are $m$ sets of edges $E_1,\ldots, E_m \subseteq E$ (say disjoint). I am interested in the problem of finding a subset $S \subseteq V$, as small as possible (or even smaller), such that the induced graph $G_S$ has at least one edge from each class $E_i$, for $i=1,\ldots, m$.

Currently, I know that this problem is set cover hard. I also have a not completely obvious (roughly) $O(\sqrt{n})$ approximation.

This seems like a natural problem - is anyone aware of any relevant references, or any better algorithms?

• this has the faint aroma of a group steiner-tree variant, but I don't have a good intuition for whether the differences are cosmetic or real. Feb 23, 2012 at 2:37
• For the version where every edge in $E$ is in some $E_i$, look for Minimum Rainbow Subgraph. Feb 23, 2012 at 7:08
• @AndreasBjörklund if you put your comment as answer, I would mark it as the correct answer. Thanks! Feb 23, 2012 at 14:51