Znalezienie dobrze wywołanego podgrupy

Otrzymujesz wykres z wierzchołkami. Jeśli chcesz, może być dwustronny. Istnieje zestawów krawędzi (powiedz rozłączny). Interesuje mnie problem znalezienia podzbioru , tak małego, jak to możliwe (lub nawet mniejszego), takiego, że indukowany wykres ma co najmniej jedną krawędź z każdej klasy , dla . $G = (V,E)$ $n$ $m$ $E_1,\ldots, E_m \subseteq E$ $S \subseteq V$ $G_S$ $E_i$ $i=1,\ldots, m$

Obecnie wiem, że ten problem jest mocno objęty. Mam też nie do końca oczywiste (z grubsza) zbliżenie. $O(\sqrt{n})$

Wydaje się to naturalnym problemem - czy ktoś zna jakieś odpowiednie odniesienia lub jakieś lepsze algorytmy?

ds.algorithms graph-theory optimization

— Sariel Har-Peled
źródło

ma słaby aromat grupowego wariantu drzewa steiner, ale nie mam dobrej intuicji, czy różnice są kosmetyczne, czy prawdziwe.

— Suresh Venkat

W przypadku wersji, w której każda krawędź

znajduje się w

, poszukaj podgrupy Minimalna tęcza.

E

$E$

E_{i}

$E_i$

— Andreas Björklund

@ AndreasBjörklund, jeśli podasz swój komentarz jako odpowiedź, oznaczę go jako poprawną odpowiedź. Dzięki!

— Sariel Har-Peled

Poszukaj minimalnego subgrafu Rainbow.

— Andreas Björklund
źródło

Wydaje się, że MRS wymaga „dokładnie jednego” zamiast „przynajmniej jednego” według tego dokumentu: sciencedirect.com/science/article/pii/S0020019010003339

— Suresh Venkat

Tak, ale przynajmniej streszczenie (nie mam dostępu do artykułu) mówi subgraf, a nie indukowany subgraf, więc myślałem, że są takie same?

— Andreas Björklund

Jest to to samo, ponieważ nie nalegają, aby wykres był indukowany subgrafem.

— Sariel Har-Peled

ah ok. mój błąd wtedy.

— Suresh Venkat