Algoritma logspace pada grafik dengan lebar pohon terbatas

Lebar pohon mengukur seberapa dekat grafik dengan pohon. NP-hard untuk menghitung lebar pohon. Algoritma pendekatan yang paling dikenal mencapai faktor . $O(\sqrt{{\log}n})$

Teorema Courcelle menyatakan bahwa setiap properti grafik yang dapat didefinisikan dalam logika orde dua monadik (MSO2) dapat diputuskan dalam waktu linier pada setiap kelas grafik dari lebar pohon yang dibatasi . Sebuah makalah baru-baru ini menunjukkan bahwa teorema Courcelle masih berlaku ketika "waktu linear" diganti dengan "logspace". Namun, ini tidak menyelesaikan kompleksitas ruang dari Graph Isomorphism pada grafik dengan lebar pohon yang dibatasi. Yang paling dikenal Hasilnya menempatkan di LogCFL.

Apakah ada masalah lain yang:

NP-hard (atau tidak diketahui berada di P) pada grafik umum, dan
diketahui dapat dipecahkan dalam waktu linear / polinomial pada grafik dengan lebar pohon terbatas, dan
TIDAK diketahui berada di LogSpace?

cc.complexity-theory ds.algorithms graph-theory space-bounded treewidth Siwa Kintali
sumber

Apa disebutkan dalam faktor pendekatan?

n

$n$

gphilip

n

$n$ adalah jumlah simpul dalam grafik input.

Shiva Kintali

Secara umum, kita dapat melakukan lebih baik daripada dalam mendekati treewidth. Algoritma pendekatan polinomial-waktu terbaik yang saya sadari mencapai faktor aproksimasi , di mana adalah treewidth dari grafik. Lihat Feige, Hajiaghayi, dan Lee, Peningkatan algoritma perkiraan untuk pemisah verteks berbobot minimum , STOC 2005.

O (\sqrt{\log n})

$O(\sqrt{\log n})$

O (\sqrt{\log w})

$O(\sqrt{\log w})$

w

$w$

gphilip

Jawaban:

Polinomial Tutte adalah contohnya.

Ini adalah generalisasi dari polinomial kromatik , yang dengan sendirinya merupakan masalah # P-hard dalam formulasi yang masuk akal. Di

Mengevaluasi Tutte Polynomial untuk Grafik Lebar-Pohon Tertebar , SD Noble, Combinatorics, Probability and Computing, 1998,

$O(f(k)n^{4+\epsilon})$ $k$ $n$

Tampaknya masalah tidak dapat diekspresikan dalam MSO2 secara langsung, meskipun saya tidak terbiasa dengan definisi terperinci ... Semoga masalah ini adalah yang Anda butuhkan!

Hsien-Chih Chang 張顯之
sumber

Apa fungsi f?

Michael Blondin

k

$k$

O (2^{(k^{3 + ϵ})})

$O(2^{(k^{3+\epsilon})})$

Makowski mengatakan bahwa "semua polinomial grafik yang dipelajari dalam literatur adalah SOL-dapat didefinisikan", dan memberikan rumusan polinomial Tutte dalam hal SOL, halaman 15 dari "Dari Kebun Binatang ke Zoologi: Menuju Teori Umum Grafik Polynomials." Dalam "Algoritma penggunaan teorema Feferman-Vaught" ia memperluas teorema Courcelle untuk menunjukkan traktabilitas untuk polinomial yang dapat didefinisikan SOL pada grafik lebar pohon yang dibatasi.

Yaroslav Bulatov