Znalezienie dobrze wywołanego podgrupy

Otrzymujesz wykres z n wierzchołkami. Jeśli chcesz, może być dwustronny. Istnieje m zestawów krawędzi E 1 , … , E m ⊆ E (powiedz rozłączny). Interesuje mnie problem znalezienia podzbioru S ⊆ V , tak małego, jak to możliwe (lub nawet mniejszego), takiego, że indukowany wykres G S ma co najmniej jedną krawędź z każdej klasy E i , dla i = 1 , … , m .$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?

Poszukaj minimalnego subgrafu Rainbow.