Berapa besar pohon treewidth yang dapat ditambah setengah dari tepi pohon?

14

Biarkan G menjadi pohon pada simpul 2n. The treewidth dari G, tw (G) = 1. Sekarang anggaplah kita menambahkan n edge ke G untuk mendapatkan grafik H. Batas atas yang mudah pada tw (H) adalah n + 1. Apakah ini pada dasarnya yang terbaik?

Tampaknya entah bagaimana tw (H) harus O (sqrt (n)), tetapi ini hanya firasat samar. Apakah kita tahu batas atas yang lebih baik daripada O (n) untuk treewidth grafik yang diperoleh dengan menambahkan n tepi ke pohon pada simpul 2n?

upper-bounds treewidth gphilip
sumber

Jawaban:

18

Model Anda tidak benar-benar kurang umum daripada bertanya tentang grafik 3-reguler yang sewenang-wenang, dan grafik 3-expander memiliki treewidth linier. Jadi saya tidak tahu tentang faktor konstan, tetapi Θ (n) adalah yang terbaik, ya.

David Eppstein
sumber
3
Terima kasih, itu menjawab pertanyaan saya. Untuk sedikit menguraikan jawaban David, misalkan H menjadi grafik 3-reguler yang terhubung pada simpul 2n. H kemudian memiliki tepi 3n. Misalkan G menjadi pohon pada simpul 2n yang diperoleh dengan menghapus n + 1 tepi dari H. Menambahkan n dari tepi ini kembali ke G akan memberi kita H '= (H minus satu sisi). Membiarkan H menjadi grafik expander dengan treewidth \ theta (n), kita melihat bahwa H 'memiliki treewidth \ theta (n) juga.
gphilip
8

Seperti yang ditunjukkan David, Anda pada dasarnya meminta batasan pada grafik yang terhubung dengan derajat rata-rata 3. Untuk kasus grafik 3-reguler yang lebih khusus, batas bawah dan atas yang berikut dapat diperoleh. Ditandai dengan pw (G) jalur lebar dari grafik G, jelas itu

(1) tw (G) <= pw (G) untuk setiap grafik G (karena dekomposisi jalur adalah dekomposisi pohon)

Terbukti dalam [1] itu

(2) Untuk setiap \ epsilon> 0, terdapat bilangan bulat n_0 sehingga untuk setiap grafik 3-reguler G pada n> = n_0 simpul, pw (G) <= n / 6 + \ epsilon * n.

Ini memberi Anda batas atas kira-kira n / 6 pada treewidth grafik 3-reguler.

Untuk batas bawah yang hampir pasti, saya kutip dari [2]:

"Karena grafik kubik acak hampir pasti memiliki lebar pembelahan setidaknya 0,101 n (Kostochka, Melnikov, 1992), mereka hampir pasti tidak memiliki pemisah ukuran lebih kecil dari n / 20" dan dengan demikian hampir pasti tidak ada pembusukan pohon dengan lebar lebih kecil dari n / 20 .

Untuk batas bawah "pasti" pada lebar pembelahan, [3] menunjukkan keluarga tak terbatas dari grafik 3-reguler, sehingga setiap grafik G = (V, E) dalam keluarga ini memiliki lebar pembelahan setidaknya 0,082 * | V |.

[1] Fedor V. Fomin, Kjartan Høie: Pathwidth dari grafik kubik dan algoritma yang tepat. Inf. Proses. Lett. 97 (5): 191-196 (2006)

[2] Jaroslav Nesetril, Patrice Ossona de Mendez: Grad dan kelas dengan ekspansi II terbatas. Aspek algoritma. Eur. J. Comb. 29 (3): 777-791 (2008)

[3] Sergei L. Bezrukov, Robert Elsässer, Burkhard Monien, Robert Preis, Jean-Pierre Tillich: Batas bawah spektral baru pada lebar pembelahan grafik. Teor Komputasi. Sci. 320 (2-3): 155-174 (2004)

Serge Gaspers
sumber
Terima kasih, Serge. Batas melalui jalur lebar mungkin lebih mudah bagi saya pada tahap ini daripada jalur melalui grafik expander; Saya belum membaca salah satu buktinya.
gphilip