# 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. – Suresh Venkat Feb 23 '12 at 2:37
• For the version where every edge in $E$ is in some $E_i$, look for Minimum Rainbow Subgraph. – Andreas Björklund Feb 23 '12 at 7:08
• @AndreasBjörklund if you put your comment as answer, I would mark it as the correct answer. Thanks! – Sariel Har-Peled Feb 23 '12 at 14:51

Look for Minimum Rainbow Subgraph.

• The MRS appears to require "exactly one" instead of "at least one" according this paper: sciencedirect.com/science/article/pii/S0020019010003339 – Suresh Venkat Feb 23 '12 at 18:23
• Yes, but at least the abstract (I've no access to the paper) says subgraph, not induced subgraph so I thought they were the same? – Andreas Björklund Feb 23 '12 at 19:06
• This is the same, since they do not insist on the graph being induced subgraph. – Sariel Har-Peled Feb 23 '12 at 22:40
• ah ok. my mistake then. – Suresh Venkat Feb 23 '12 at 22:51