Нахождение хорошего индуцированного подграфа

Вам дан граф с вершинами. Это может быть двудольный, если хотите. Существует наборов ребер (скажем, дизъюнкт). Меня интересует проблема нахождения как можно меньшего (или даже меньшего) подмножества , такого, чтобы индуцированный граф имел хотя бы одно ребро из каждого класса , для , $G = (V,E)$ $n$ $m$ $E_1,\ldots, E_m \subseteq E$ $S \subseteq V$ $G_S$ $E_i$ $i=1,\ldots, m$

В настоящее время я знаю, что эта проблема ставится на укрытие. У меня также есть не совсем очевидное (примерно) приближение. $O(\sqrt{n})$

Это кажется естественной проблемой - кто-нибудь знает какие-либо соответствующие ссылки или какие-либо лучшие алгоритмы?

ds.algorithms graph-theory optimization Сариэль Хар-Пелед
источник

у этого есть слабый аромат варианта дерева штейнера группы, но у меня нет хорошей интуиции для того, являются ли различия косметическими или реальными.

Суреш Венкат

Для версии, где каждое ребро в находится в некотором , ищите Minimum Rainbow Subgraph.

E

$E$

E_{i}

$E_i$

Андреас Бьёрклунд

@ AndreasBjörklund, если вы оставите свой комментарий как ответ, я бы отметил его как правильный ответ. Благодарность!

Сариэль Хар-Пелед

Ответы:

Ищите Минимальный Подграф Радуги.

Андреас Бьёрклунд
источник

Согласно этому документу, для MRS требуется «ровно один» вместо «хотя бы один»: sciencedirect.com/science/article/pii/S0020019010003339

Суреш Венкат

Да, но, по крайней мере, в реферате (у меня нет доступа к статье) написано подграф, а не вызванный подграф, поэтому я подумал, что они одинаковые?

Андреас Бьёрклунд

Это то же самое, поскольку они не настаивают на том, чтобы граф был индуцированным подграфом.

Сариэль Хар-Пелед

Ах хорошо. моя ошибка тогда

Суреш Венкат