Menemukan subgraf yang diinduksi baik

Anda diberi grafik dengan simpul. Mungkin bipartit jika Anda mau. Ada set tepi (katakanlah disjoint). Saya tertarik pada masalah menemukan subset , sekecil mungkin (atau bahkan lebih kecil), sehingga grafik yang diinduksi memiliki setidaknya satu sisi dari setiap kelas , untuk . $G = (V,E)$ $n$ $m$ $E_1,\ldots, E_m \subseteq E$ $S \subseteq V$ $G_S$ $E_i$ $i=1,\ldots, m$

Saat ini, saya tahu bahwa masalah ini disetel menjadi sulit. Saya juga memiliki tidak sepenuhnya jelas (kira-kira) perkiraan. $O(\sqrt{n})$

Ini sepertinya masalah alami - adakah yang mengetahui referensi yang relevan, atau algoritma yang lebih baik?

ds.algorithms graph-theory optimization Sariel Har-Peled
sumber

ini memiliki aroma samar dari varian steiner-tree group, tetapi saya tidak memiliki intuisi yang baik apakah perbedaannya kosmetik atau nyata.

Suresh Venkat

Untuk versi di mana setiap sisi dalam

ada di beberapa

, cari Minimum Rainbow Subgraph.

E

$E$

E_{i}

$E_i$

Andreas Björklund

@ AndreasBjörklund jika Anda memberikan komentar sebagai jawaban, saya akan menandainya sebagai jawaban yang benar. Terima kasih!

Sariel Har-Peled

Jawaban:

Carilah Minimum Rainbow Subgraph.

Andreas Björklund
sumber

MRS tampaknya membutuhkan "tepat satu" daripada "setidaknya satu" menurut makalah ini: sciencedirect.com/science/article/pii/S0020019010003339

Suresh Venkat

Ya, tapi setidaknya abstrak (saya tidak punya akses ke kertas) mengatakan subgraph, bukan subgraph yang diinduksi jadi saya pikir mereka sama?

Andreas Björklund

Ini sama, karena mereka tidak bersikeras pada grafik yang diinduksi subgraf.

Sariel Har-Peled

ah baiklah kesalahan saya kalau begitu.

Suresh Venkat