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?

  • $\begingroup$ 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. $\endgroup$ Feb 23, 2012 at 2:37
  • 1
    $\begingroup$ For the version where every edge in $E$ is in some $E_i$, look for Minimum Rainbow Subgraph. $\endgroup$ Feb 23, 2012 at 7:08
  • $\begingroup$ @AndreasBjörklund if you put your comment as answer, I would mark it as the correct answer. Thanks! $\endgroup$ Feb 23, 2012 at 14:51

1 Answer 1


Look for Minimum Rainbow Subgraph.

  • 2
    $\begingroup$ The MRS appears to require "exactly one" instead of "at least one" according this paper: sciencedirect.com/science/article/pii/S0020019010003339 $\endgroup$ Feb 23, 2012 at 18:23
  • 3
    $\begingroup$ 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? $\endgroup$ Feb 23, 2012 at 19:06
  • $\begingroup$ This is the same, since they do not insist on the graph being induced subgraph. $\endgroup$ Feb 23, 2012 at 22:40
  • 1
    $\begingroup$ ah ok. my mistake then. $\endgroup$ Feb 23, 2012 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.