Finding good induced subgraph

Question

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 02: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 07: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

score 15 · Accepted Answer · answered Feb 23 '12 at 15:13

15

Look for Minimum Rainbow Subgraph.

answered Feb 23 '12 at 15:13

Andreas Björklund

3,254
1
22
23

2

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 Feb 23 '12 at 18:23
3

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
1

ah ok. my mistake then. – Suresh Venkat Feb 23 '12 at 22:51

Finding good induced subgraph

1 Answers1