Sepasang siklus titik terpisah di grafik yang diarahkan

13

Apa algoritma deterministik tercepat yang diketahui yang dapat mengenali grafik berarah dengan sepasang siklus disintegrasi titik? Saya tahu grafik dengan min outdegree three selalu memiliki pasangan seperti itu ( Thomassen'83 ), tetapi meskipun demikian saya tidak dapat menemukan algoritma yang efisien dalam kasus umum. Adakah yang tahu referensi untuk ini?

reference-request Andreas Björklund
sumber
1
Untuk grafik tidak terarah, itu NP-lengkap untuk mengenali grafik dengan vertex mengatur dipartisi menjadi dua siklus disjoint vertex ukuran sama.
Mohammad Al-Turkistany
1
Karakterisasi untuk grafik yang tidak diarahkan juga non-trival, karena Lovasz, dan dapat ditemukan misalnya di sini: arxiv.org/abs/1601.03791 .
domotorp

Jawaban:

9

Menurut Grohe dan Gruber " Parameterized approximability dari masalah siklus menguraikan " (ICALP 2007) ada sebuah algoritma untuk menemukan siklus vertex-menguraikan dalam digraf, dalam waktu n f ( k ) untuk beberapa fungsi f (polinomial untuk tetap k tetapi bukan FPT) dalam bagian 5 dari Reed, Robertson, Seymour dan Thomas, " Pengemasan sirkuit terarah " (Combinatorica 1996) (yang pada gilirannya menggunakan teorema 3 dari " Masalah hemeomorfisme subgraph yang diarahkan " dari Fortune, Hopcroft, dan Wyllie.)knf(k)fk

David Eppstein
sumber
2
Hanya ingin menambahkan komentar kecil. Mungkin bermanfaat untuk melihat treewidth diarahkan dan teorema grid baru Kreutzer dan Kawarabayashi yang menyoroti beberapa teknik tambahan dalam kertas etal Reed. Mereka menjelajahi teorema minor grid terarah untuk membuktikan teorema Erdos-Posa untuk grafik berarah, tetapi berguna untuk melihat skema tingkat tinggi berdasarkan teorema grid terarah.
Chandra Chekuri
2

Untuk digraf sangat terhubung dan digraf G umum , ada algoritma yang berjalan di | G | f ( k + | H | ) dan menemukan k model kupu-kupu disjoint H dalam G jika ada. Untuk menemukan dua siklus terpisah kami memiliki | H | = 1 , k = 2 . Ini adalah konsekuensi langsung dari bukti algoritme dari Teorema 4.3 inHG|G|f(k+|H|)kHG|H|=1,k=2

https://arxiv.org/abs/1603.02504

Saeed
sumber