19
$\begingroup$

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?

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

Look for Minimum Rainbow Subgraph.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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