Menemukan subgraph dengan treewidth tinggi dan derajat konstan

9

Saya diberi grafik dengan treewidth dan derajat sewenang-wenang, dan saya ingin menemukan subgraf dari (belum tentu merupakan subgraf yang diinduksi) sedemikian rupa sehingga memiliki derajat yang konstan dan treewidth-nya setinggi mungkin. Secara resmi masalah saya adalah sebagai berikut: telah memilih derajat terikat , apa fungsi "terbaik" sedemikian rupa sehingga, dalam grafik G dengan treewidth k , saya dapat menemukan (semoga efisien) subgraph H dari G dengan derajat maksimal \ leq d dan treewidth f (k)G H G H d N f : NN G k H G d f ( k )kHGHdNf:NNGkHGdf(k).

Jelas kita harus mengambil d3 karena tidak ada grafik treewidth tinggi dengan derajat maksimal <3 . Untuk d=3 saya tahu bahwa Anda dapat mengambil f sedemikian rupa sehingga f(k)=Ω(k1/100) atau lebih, dengan menarik hasil ekstraksi minor grid Chekuri dan Chuzhoy (dan menggunakannya untuk mengekstraksi yang tinggi -treewidth degree-3 graph, misalnya dinding, sebagai minor topologi), dengan perhitungan subgraph yang layak (dalam RP). Namun, ini adalah hasil yang sangat kuat dengan bukti rumit, jadi rasanya salah untuk menggunakannya untuk apa yang tampak seperti masalah yang lebih sederhana: Aku akan seperti untuk menemukan setiapsubgraph tingkat tinggi, treewidth tinggi, bukan yang spesifik seperti dalam hasilnya. Lebih jauh, ikatan f tidak sebaik yang saya harapkan. Tentu, diketahui bahwa itu dapat dibuat Ω(k1/20) (hingga menyerah efisiensi perhitungan), tetapi saya berharap untuk sesuatu seperti Ω(k) . Jadi, apakah mungkin untuk menunjukkan bahwa, mengingat grafik G dari treewidth k , ada subgraf G dengan derajat konstan dan treewidth linier dalam k ?

Saya juga tertarik pada pertanyaan yang sama persis untuk pathwidth daripada treewidth. Untuk pathwidth, saya tidak tahu analog dengan ekstraksi minor grid, jadi masalahnya tampak lebih misterius ...

a3nm
sumber

Jawaban:

12

Lihat kertas karya Julia Chuzhoy dan saya sendiri tentang sparsifier Treewidth. Kami menunjukkan bahwa seseorang dapat memperoleh subgraph dari tingkat paling banyak 3 dengan treewidth di mana k adalah treewidth dari G . https://arxiv.org/abs/1410.1016 Buktinya lebih pendek dari yang ada pada kisi-kisi di bawah umur, tetapi masih tidak semudah itu dan dibangun di atas beberapa alat sebelumnya.Ω(k/halHailylHaig(k))kG

Misalkan Anda puas target yang lebih mudah - tingkat 4 dan treewidth maka Anda bisa mendapatkan jauh lebih mudah melalui hasil Reed dan Kayu di grid-seperti anak di bawah umur. https://arxiv.org/abs/0809.0724Ω(k1/4)

Hasil mudah lainnya yang dapat Anda peroleh adalah yang berikut ini yang merupakan titik awal untuk beberapa bukti yang lebih terlibat. Anda bisa mendapatkan subgraph dari dan treewidth Ω ( k / p o l y l o g ( k ) ) . Anda dapat melihat kertas spewifier treewidth untuk argumen untuk mencapai ini.catatan2(k)Ω(k/halHailylHaig(k))

Chandra Chekuri
sumber
1
Komentar tambahan. Apakah seseorang bisa mendapatkan subgraph dengan treewidth dan derajat konstan adalah masalah terbuka yang sangat menarik. Kami mengajukan pertanyaan ini di kertas spewifier treewidth tetapi tidak memiliki jawaban yang tepat. Satu grafik menarik yang ditanyakan oleh Bart Jansen adalah hypercube pada n node yang memiliki treewidth Θ ( n / log nΩ(k)n dan derajat awal Θ ( log n ) . Θ(n/logn)Θ(logn)
Chandra Chekuri
Terima kasih telah menunjuk ke Reed dan Wood! Saya akan mengisi rinciannya. Thm 1.2 dari makalah mereka mengatakan bahwa grafik G dengan treewidth berisi grid-like-minor of order l. Sekarang grid-like-minor M adalah subgraf G yang dibentuk dari lintasan dengan grafik persimpangan bipartit H, sehingga setiap simpul dalam M termasuk paling banyak 2 lintasan M (jika tidak itu adalah segitiga dalam H), maka M memiliki derajat maksimal 4. Lebih lanjut, M memiliki treewidth Ω ( l ) : memang setiap pohon Desember dari lebar k menghasilkan Desember pohon dengan lebar H <2k (mengganti setiap simpul dengan jalur anggota, paling banyak 2), dan H memilikiΩ(l4halHailylHaig(l))Ω(l) sebagai anak di bawah umur. Kl
a3nm
Sekali lagi, ini sangat membantu, terima kasih. Sangat menarik bahwa pertanyaan untuk treewidth linier masih terbuka. (Yang mengatakan, jika saya mengerti dengan benar, Dugaan 1.2 di kertas sparsifier Anda adalah tentang masalah yang sedikit berbeda: itu membutuhkan subgraph untuk menjadi subdivisi dari beberapa H ukuran polinomial dalam k, sedangkan saya tidak meminta ini dan hanya ingin subgraph memiliki derajat konstan.) Satu hal terakhir: apakah Anda tahu apakah ada yang diketahui tentang masalah terbuka ini tetapi untuk pathwidth daripada treewidth? Terima kasih lagi!
a3nm
@ A3nm mengapa Anda terkejut bahwa pertanyaan tentang treewidth linier terbuka? Saat ini kami tidak memiliki perkiraan faktor konstan untuk treewidth. Mengenai pathwidth, sekarang satu-satunya cara untuk pathwidh perkiraan adalah melalui hubungan antara treewdith dan pathwidth yang menunjukkan . Melalui spewifikasi treewidth kita juga bisa mendapatkan sparsifikasi pathwidth tetapi kita kehilangan faktor log. Akan lebih baik jika ini hanya faktor log pw (G) tapi saya tidak yakin bagaimana melakukannya atau apakah itu diketahui. tw(G)halw(G)HAI(catatann)tw(G)
Chandra Chekuri
Terima kasih atas penjelasan Anda tentang status threewidth linier, dan terima kasih juga untuk penjelasan penyebaran bandwidth. Hal terakhir yang Anda sebutkan adalah jenis hasil yang kami butuhkan; Sayang sekali pertanyaannya masih terbuka. Bagaimanapun, terima kasih banyak lagi atas penjelasan Anda!
a3nm