Kompleksitas menentukan apakah grafik tetap merupakan minor dari grafik lainnya

Hasil oleh Robertson dan Seymour menunjukkan sebuah algoritma untuk menguji apakah grafik tetap adalah minor dari . Saya punya dua setengah pertanyaan tentang topik ini:$O(n^3)$$G$$H$

1) Tampaknya telah ada peningkatan pada algoritma ini sejak. Apa algoritma paling terkenal saat ini?

2a) Apa yang orang duga sebagai ikatan optimal?

Algoritma Mohar untuk menanamkan pada permukaan yang tetap dan algoritma Kawarabayashi untuk mengenali grafik -apex$k$ memutuskan keanggotaan dari grafik yang ditandai oleh anak di bawah umur yang terlarang dalam waktu linier, memotivasi pertanyaan terakhir:

2b) Apakah ada alasan untuk curiga bahwa kita dapat melakukan ini dalam waktu linier?

Tentu saja, jika seseorang sudah menemukan algoritma linear-waktu, dua pertanyaan terakhir itu konyol. :)

Ada pracetak oleh Ken-ichi Kawarabayashi, Yusuke Kobayashi, dan Bruce Reed yang mengklaim algoritma waktu kuadratik: " Masalah jalur terputus-putus dalam waktu kuadratik ". Itu diformat sebagai pengiriman konferensi daripada makalah jurnal jadi saya tidak yakin itu mungkin untuk memverifikasi rincian, meskipun (saya belum benar-benar mencoba, sendiri).

Sebuah survei yang sangat baru-baru ini oleh Kawarabayashi mengutip ini sebagai hasil yang paling dikenal untuk masalah jalur terpisah terkait erat: Ken-ichi Kawarabayashi (2011), "Masalah Jalur Terpisah: Algoritma dan Struktur", WALCOM: Algoritma dan Komputasi, LNCS 6552, pp 2–7, doi: 10.1007 / 978-3-642-19094-0_2 .

Saya tidak tahu apakah ini berarti bahwa klaim dalam komentar Kothari tidak jelas atau apakah ini berarti bahwa masih pada tahap awal ditulis.$O(n\log n)$

Sebuah kertas baru-baru ini oleh Isolde Adler1, Frederic Dorn, Fedor V. Fomin, Ignasi Sau dan Dimitrios M. Thilikos disebut Cepat Kecil Pengujian di planar Grafik menunjukkan bahwa ketika mencari minor pada simpul dalam graf planar , ini dapat dilakukan dalam waktu . Sedangkan ketergantungan pada tidak sebagus seperti yang disebutkan dalam jawaban dengan David, ketergantungan pada dari pekerjaan ini jauh lebih unggul.$H$$h$ $G$$2^{O(h)} n + O(n^2 \log n)$$n$$h$