<p>Look for Minimum Rainbow Subgraph.</p>

CC BY-SA 3.0
2012-02-23T18:23:12.563Z
The MRS appears to require "exactly one" instead of "at least one" according this paper: http://www.sciencedirect.com/science/article/pii/S0020019010003339
Suresh Venkat
CC BY-SA 3.0
2012-02-23T19:06:32.693Z
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
CC BY-SA 3.0
2012-02-23T22:40:22.193Z
This is the same, since they do not insist on the graph being induced subgraph.
Sariel Har-Peled
CC BY-SA 3.0
2012-02-23T22:51:59.227Z
ah ok. my mistake then.
Suresh Venkat
CC BY-SA 3.0
2012-02-23T15:13:20.467Z
2012-02-23T15:13:20.467Z
Andreas Björklund
<p>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$. </p>

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

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

CC BY-SA 3.0
2012-02-23T02:37:34.677Z
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
CC BY-SA 3.0
2012-02-23T07:08:20.550Z
For the version where every edge in $E$ is in some $E_i$, look for Minimum Rainbow Subgraph.
Andreas Björklund
CC BY-SA 3.0
2012-02-23T14:51:06.500Z
@AndreasBjörklund if you put your comment as answer, I would mark it as the correct answer. Thanks!
Sariel Har-Peled
<ds.algorithms><graph-theory><optimization>
Finding good induced subgraph
Sariel Har-Peled
# Finding good induced subgraph

(Asked by: username_0 on 2012-02-22)

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?

**Tags:** ds.algorithms, graph-theory, optimization

> **Comments:**
> **username_1**: 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.  
> **username_2**: For the version where every edge in $E$ is in some $E_i$, look for Minimum Rainbow Subgraph.  
> **username_0**: @AndreasBjörklund if you put your comment as answer, I would mark it as the correct answer. Thanks!  

---

## 1 answers

### Answer by username_2 on 2012-02-23. Score: 15 | Accepted answer

Look for Minimum Rainbow Subgraph.

> **Comments:**
> **username_1**: The MRS appears to require "exactly one" instead of "at least one" according this paper: http://www.sciencedirect.com/science/article/pii/S0020019010003339  
> **username_2**: 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?  
> **username_0**: This is the same, since they do not insist on the graph being induced subgraph.  
> **username_1**: ah ok. my mistake then.  

---

