Menemukan subgraph dengan treewidth tinggi dan derajat konstan

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 dengan treewidth , saya dapat menemukan (semoga efisien) subgraph dari dengan derajat maksimal dan treewidth $G$ $k$ $H$ $G$ $H$ $d \in \mathbb{N}$ $f : \mathbb{N} \to \mathbb{N}$ $G$ $k$ $H$ $G$ $\leq d$ $f(k)$ .

Jelas kita harus mengambil $d \geq 3$ 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) = \Omega(k^{1/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 $\Omega(k^{1/20})$ (hingga menyerah efisiensi perhitungan), tetapi saya berharap untuk sesuatu seperti $\Omega(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 ...

co.combinatorics treewidth graph-minor bounded-degree a3nm
sumber

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 adalah treewidth dari . 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. $\Omega(k/polylog(k))$ $k$ $G$

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 $\Omega(k^{1/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 . Anda dapat melihat kertas spewifier treewidth untuk argumen untuk mencapai ini. $\log^2(k)$ $\Omega(k/\mathsf{polylog}(k))$

Chandra Chekuri
sumber

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

node yang memiliki treewidth

Ω (k)

$\Omega(k)$

n

$n$

dan derajat awal

Θ (n / \log n)

$\Theta(n/\log n)$

Θ (\log n)

$\Theta(\log n)$

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

: 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

Ω (l^{4} p o l y l o g (l))

$\Omega(l^4 polylog(l))$

Ω (l)

$\Omega(l)$

sebagai anak di bawah umur.

K_{l}

$K_l$

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.

t w (G) \leq p w (G) \leq O (\log n) t w (G)

$tw(G) \le pw(G) \le O(\log n) 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

Menemukan subgraph dengan treewidth tinggi dan derajat konstan

Jawaban: