apa yang mudah untuk grafik dengan pengecualian kecil?

31

Perkiraan jumlah pewarnaan tampaknya mudah pada grafik dengan pengecualian kecil menggunakan algoritma oleh Jung / Shah. Apa contoh lain dari masalah yang sulit pada grafik umum tetapi mudah pada grafik kecil-dikecualikan?

Pembaruan 10/24 Tampaknya mengikuti hasil Grohe bahwa rumus yang FPT untuk menguji pada grafik terikat-treewidth adalah FPT untuk menguji pada grafik kecil yang tidak termasuk. Sekarang pertanyaannya adalah - bagaimana hubungannya dengan keterlacakan menghitung penugasan yang memuaskan dari formula tersebut?

Pernyataan di atas salah. MSOL adalah FPT pada grafik lebar pohon terbatas, namun 3-colorability adalah NP-lengkap pada grafik planar yang tidak termasuk kecil.

ds.algorithms graph-theory graph-minor Yaroslav Bulatov
sumber

23

Hasil paling umum yang diketahui adalah oleh Grohe. Ringkasan disajikan pada bulan Juli 2010:

Martin Grohe, Definisi Tetap-Titik dan Waktu Polinomial pada Grafik dengan Anak-anak yang Dikecualikan , LICS 2010. ( PDF )

Singkatnya, setiap pernyataan yang dapat diekspresikan dalam logika titik tetap dengan penghitungan memiliki algoritma waktu polinomial pada kelas grafik dengan setidaknya satu minor yang dikecualikan. (FP + C adalah logika orde pertama ditambah dengan operator titik tetap dan predikat yang memberikan kardinalitas set simpul yang dapat didefinisikan). Gagasan utamanya adalah bahwa mengecualikan minor memungkinkan grafik di kelas untuk memerintahkan dekomposisi treelike yang dapat didefinisikan dalam logika titik tetap (tanpa menghitung).

~~Jadi kelas besar jawaban untuk pertanyaan Anda dapat diperoleh dengan mempertimbangkan properti yang dapat didefinisikan dalam FP + C tetapi sulit untuk dihitung.~~

Sunting: Saya tidak yakin ini benar-benar menjawab pertanyaan Anda, apalagi untuk pembaruan Anda. Pointer ke dan pernyataan hasil Grohe benar, tetapi saya tidak berpikir bahwa teks yang keluar cocok untuk pertanyaan Anda. (Terima kasih kepada Stephan Kreutzer karena menunjukkan hal ini.) Mungkin perlu diperjelas: apakah Anda menginginkan masalah penghitungan yang sulit secara umum tetapi mudah pada kelas kecil yang dikecualikan, atau masalah keputusan?

András Salamon
sumber

1

Menarik ... Saya ingin tahu seperti apa dekomposisi seperti ini untuk grafik planar

Yaroslav Bulatov

2

Teorema yang berguna yang saya temukan adalah bahwa properti dapat diekspresikan dalam FP + C jika itu dapat ditentukan dalam waktu polinomial pada dua grafik terikat. Sekarang pertanyaannya adalah - bagaimana kompleksitas masalah keputusan FP + C berhubungan dengan kompleksitas masalah penghitungan analog?

Yaroslav Bulatov

@Yaroslav: Bisakah Anda memberikan referensi untuk ini setelah ditulis? Terima kasih.

gphilip

3

Lol, saya tidak benar-benar menemukannya, saya "menemukannya" di halaman 2 dari "Logika, Grafik, dan Algoritma" Grohe "

Yaroslav Bulatov

18

Sebuah properti menarik dari keluarga grafik minor-tertutup adalah bahwa mereka telah membatasi degenerasi . Ini berarti bahwa semua masalah yang mudah pada grafik degenerasi terbatas mudah pada grafik dari keluarga kecil-tertutup.

Jadi, misalnya, menemukan jika grafik berisi sebuah klik dari ukuran k biasanya masalah yang sulit dan algoritma terbaik seperti . Namun, jika kita tahu bahwa degenerasi adalah konstan, maka klik-k dapat ditemukan dalam waktu linier, yaitu waktu O (n). Artikel Wikipedia tentang masalah klik memberikan beberapa informasi tentang ini juga. (Waktu berjalan yang tepat adalah sesuatu seperti .) Algoritma ini adalah oleh Chiba dan Nishizeki . $O(n^k)$ $O(k d(G)^k n)$

Contoh lain dapat ditemukan dalam jawaban ini oleh David Eppstein di MathOverflow untuk pertanyaan serupa tentang grafik dengan degenerasi terbatas.

Robin Kothari
sumber

5

Makalah saya arxiv.org/abs/1006.5440 memiliki beberapa hasil lebih baru tentang daftar klik dengan degenerasi rendah termasuk runtime

agak lebih baik

untuk daftar semua klik yang maksimal.

O (d n 3^{d / 3})

$O(dn3^{d/3})$

David Eppstein

Saya tidak dapat melihat apa hubungan antara minor-tertutup (jawaban Anda), dan grafik kecil-dikecualikan (pertanyaan). Juga mengatur semua grafik lengkap tertutup kecil, tetapi mereka tidak degenerasi terbatas.

Saeed

Minor-closed = minor-dikecualikan. Semua keluarga grafik minor-tertutup non-sepele memiliki degenerasi terbatas. Saya seharusnya menambahkan "non-sepele" ke pernyataan asli saya.

Robin Kothari

Pertama-tama minor closed! = Dikecualikan minor (bukan dikecualikan minor

minor closed), jika tidak, Anda dapat memberikan banyak aproksimasi baru dan algoritma parametrized untuk banyak kelas grafik yang padat. Juga apa grafik tertutup minor non-sepele? misal grafik treewidth paling banyak f (| G |) trivial atau non-trivial? atau kelas grafik padat (yang tertutup kecil dan terurut dengan baik), apakah sepele tutupan kecil atau non-sepele? Definisi Anda tidak jelas, dan pembaca tidak dapat menebak apa yang ada dalam pikiran Anda (dan beberapa bagian dari definisi Anda salah seperti yang saya nyatakan di awal).

\subset

$\subset$

Saeed

Saya dapat memberi tahu Anda apa yang saya maksud dengan keluarga grafik minor-tertutup.

adalah minor

jika

dapat diperoleh dari

dengan menghapus tepi, menghapus simpul yang terisolasi atau tepi yang berkontraksi. Kelompok grafik adalah seperangkat grafik tanpa label yang tidak diberi label

(biasanya himpunan tak terbatas).

adalah keluarga kecil tertutup jika untuk semua

di

, semua anak di bawah umur dari

juga di

. Satu keluarga adalah non-sepele jika bukan set dari semua grafik. Grafik treewidth

(untuk konstanta

) kecil-tertutup tetapi grafik treewidth

H

$H$

G

$G$

H

$H$

G

$G$

F

$F$

F

$F$

G

$G$

F

$F$

G

$G$

F

$F$

k

$k$

k

$k$

secara umum tidak tertutup. Ini adalah bagaimana saya memahaminya. Tentu saja saya bisa salah.

f (| G |)

$f(|G|)$

Robin Kothari

15

Sebagai pelengkap, properti lain yang berguna untuk algoritma pada grafik kecil-dikecualikan adalah bahwa grafik ini memiliki pemisah kecil . Lebih tepatnya, karena

Algoritma waktu linear untuk menemukan pemisah dalam grafik tidak termasuk minor , Bruce Reed dan David R. Wood, ACM Transactions on Algorithms, 2009,

ada algoritma waktu linear untuk menemukan pemisah ukuran , atau algoritma waktu untuk menemukan pemisah ukuran . $O(n^{2/3})$ $O(n^{3/2} + m)$ $O(n^{1/2})$

Pemisah baik untuk teknik pemrograman dinamis , dan banyak masalah NP-lengkap terbukti memiliki algoritma cepat dengan rasio perkiraan yang baik, katakanlah solusinya berada dalam faktor konstan yang optimal, atau bahkan PTAS. Grafik planar , dan secara umum, grafik genus terikat adalah titik awal yang baik ketika mencoba untuk memecahkan masalah pada grafik kecil-dikecualikan.

Hsien-Chih Chang 張顯之
sumber

Adakah ide jika separator membantu menghitung jumlah pewarnaan yang tepat?

Yaroslav Bulatov

1

tidak juga, mungkin kertas yang disebutkan oleh Ian membantu lebih baik. Perpanjangan hasil ada di "Algoritma Perkiraan melalui Penguraian Kontraksi" oleh penulis yang sama di SODA '07.

Hsien-Chih Chang 張顯之

15

$O(1)$

Teori Algoritma Grafik Minor: Dekomposisi, Perkiraan, dan Pewarnaan oleh Demaine, Hajiaghayi, dan Kawarabayashi

Makalah ini memberikan versi algoritmik dari dekomposisi tertentu (agak rumit untuk dijelaskan) untuk grafik kecil-kecil yang dijamin oleh teorema Robertson & Seymour, yang menghasilkan sejumlah hasil perkiraan yang lebih baik ini. Lihat juga referensi di dalamnya.

Ian
sumber

Terima kasih, itu cukup menarik ... Saya menemukan deskripsi yang lebih mudah diakses dari algoritma dekomposisi di Grohe "Logic, Graphs, and Algorithms"

Yaroslav Bulatov

0

$K_5$ $K_{3,3}$

$H$ $H$

$K_t$ $(t-1)$ $K_t$ $(t-1)$ $t− 2$

Rupei Xu
sumber

apa yang mudah untuk grafik dengan pengecualian kecil?

Jawaban: