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?

Improve this question
$\endgroup$
3
  • $\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, 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$
    – Andreas Björklund
    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$
    – Sariel Har-Peled
    Feb 23, 2012 at 14:51

1 Answer 1

Reset to default
15
$\begingroup$

Look for Minimum Rainbow Subgraph.

Improve this answer
$\endgroup$
4
  • 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, 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$
    – Andreas Björklund
    Feb 23, 2012 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, 2012 at 22:40
  • 1
    $\begingroup$ ah ok. my mistake then. $\endgroup$
    – Suresh Venkat
    Feb 23, 2012 at 22:51

Your Answer

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

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