Kompleksitas homomorfisme digraf ke siklus yang berorientasi

Mengingat tetap diarahkan grafik (digraf) , yang -coloring masalah keputusan menanyakan apakah digraph masukan memiliki homomorfisma untuk . (A homomorfisme ke adalah pemetaan dari ke yang mempertahankan busur, yaitu, jika adalah busur , maka adalah busur dari )D G V ( G ) V ( D ) u v G f ( u ) f ( v ) $D$$D$$G$G D $D$$G$$D$$f$$V(G)$$V(D)$$uv$$G$$f(u)f(v)$$D$

Kelas masalah WARNA sangat terkait dengan Dichotomy Conjecture for CSPs yang dinyatakan oleh Feder dan Vardi (dapat diakses dengan citeseer ).$D$

Dalam makalah tahun 2001 ini (dapat diakses di halaman penulis, di sini ), Feder membuktikan teorema dikotomi ketika adalah siklus berorientasi (oleh siklus berorientasi Maksudku siklus tidak terarah di mana setiap tepi diganti dengan busur tunggal, yang dapat berorientasi sewenang-wenang) , dengan kata lain, ia menunjukkan bahwa untuk setiap siklus berorientasi D , D- WARNA dapat diselesaikan dengan waktu polinomial atau lengkap NP.$D$$D$$D$

Sayangnya, klasifikasi Feder sangat nontrivial dan tidak eksplisit, karena kompleksitas banyak kasus terkait dengan kompleksitas varian terbatas tertentu dari SAT yang bergantung pada orientasi. Dengan melihat kertas, saya belum dapat menentukan jawaban atas pertanyaan saya:

Pertanyaan: Berapa ukuran terkecil dari siklus D yang berorientasi $D$sehingga $D$ WARNA adalah NP-complete?

Jawabannya mungkin dinyatakan di suatu tempat dalam literatur, tetapi saya tidak dapat menemukannya.

Edit:Biarkan saya memberikan detail lebih lanjut tentang klasifikasi Feder. Feder menunjukkan bahwa setiap siklus berorientasi NP-lengkap harus seimbang, yaitu, memiliki jumlah busur yang sama di kedua arah (maka ia memiliki urutan genap). Kemudian, pertimbangkan "level" yang disebabkan oleh orientasi (mulailah berkeliling siklus pada titik sembarang; jika busur melengkung ke kanan, Anda naik sebesar 1, jika busur melengkung ke kiri, Anda turun sebesar 1). Kemudian, jika ada paling banyak satu "run top-bottom", itu polinomial. Jika ada setidaknya 3 "berjalan" dan siklus adalah inti, itu NP-lengkap. (Dalam contoh András dari komentar, ada tiga "berjalan" seperti itu, tetapi siklus ini bukan inti.) Kasing yang paling sulit adalah yang memiliki dua "lari dari atas". Beberapa sulit, beberapa jumlahnya banyak, dan Feder mengaitkannya dengan masalah SAT khusus untuk mendapatkan dikotomi.

Sebagai pertanyaan antara: Apa siklus berorientasi terkecil yang memiliki tiga putaran "atas-bawah" dan merupakan inti? Contoh seperti itu akan lengkap dengan diskusi di atas.

Untuk pertanyaan antara (inti dengan tiga putaran atas-bawah), bagaimana dengan ini?

Beberapa notasi: Saya akan menjelaskan menjalankan dengan kata-kata di , dengan misalnya sesuai dengan subgraph . Level meningkat pada arc dan berkurang pada arc, dan saya berasumsi bahwa minimumnya adalah . Beberapa kendala langsung adalah: l l r l ⋅ ← ⋅ ← ⋅ → ⋅ ← ⋅ r l $\{l,r\}^*$$llrl$$\cdot\leftarrow\cdot\leftarrow\cdot\to\cdot\leftarrow\cdot$$r$$l$$0$

• Tidak boleh ada run yang hanya terdiri dari atau hanya , karena jika tidak ada homomorfisme yang jelas dari untuk menjalankan ini (memetakan setiap simpul ke yang dengan tingkat yang sama). Ini juga menyiratkan bahwa level maksimum harus minimal .r D D $l$$r$$D$$D$$3$
• Jika level maksimum adalah , maka semua menjalankan top-bottom (resp bottom-top) akan dari bentuk (resp. ; sekali lagi tidak terlalu sulit untuk menemukan homomorfisme dari ke run yang meminimalkan .l l r ( l r ) i l l r r l ( r l ) i r r ) D $3$$llr(lr)^ill$$rrl(rl)^irr)$$D$$i$

Namun, untuk level maksimum ada solusi, dengan panjang : pertimbangkan diberikan oleh . Ini memiliki operasi top-bottom yang diperlukan dan merupakan inti (lihat di bawah). Dengan kendala di atas, itu harus minimal, karena masing-masing menjalankan hanya memiliki satu tepi "mundur".36 D ( r r r l r r l l l r l l ) $4$$36$$D$$(rrrlrrlllrll)^3$

Untuk meyakinkan diri sendiri bahwa ini adalah sebuah inti, mari beri nama simpulnya terlebih dahulu ( ). Simpul bawah (yaitu level ) adalah . Homomorfisme dari hingga subgraf harus mempertahankan level, dan khususnya ; modulo automorfisme yang jelas , cukup untuk mempertimbangkan kasus . Pertimbangkan lingkungan dalam (dijelaskan dengan level): 0 v 1 , v 13 , v 25 φ D φ ( v 1 ) ∈ { v 1 , v 13 , v 25 } v i ↦ v i + 12 φ ( v 1 ) = v 1 v 1$v_1,\ldots,v_{36}$$0$$v_1,v_{13},v_{25}$$\varphi$$D$$\varphi(v_1)\in\{v_1,v_{13},v_{25}\}$$v_i\mapsto v_{i+12}$$\varphi(v_1)=v_1$$v_1$$D$

$v_{34}(1)\to v_{35}(2)\leftarrow v_{36}(1)\leftarrow v_1(0)\to v_2(1)\to v_3(2)\to v_4(3)\leftarrow v_5(2)\to v_6(3)\to v_7(4)$

Dimulai dengan , kami memiliki . Tetapi jika , maka , dan kami tidak memiliki nilai yang mungkin untuk . Kita mendapatkan . Berikutnya , tetapi untuk kita mendapatkan , tanpa nilai yang mungkin untuk . Jadi harus menjadi identitas pada seluruh proses , dan dengan mengulangi argumen yang sama untuk sisa proses, hal yang sama berlaku pada semua φ ( v 2 ) ∈ { v 36 , v 2 } φ ( v 2 ) = v 36 φ ( v 3 ) = v 35 φ ( v 4 ) φ ( v 2 ) = v 2 , φ ( v 3 ) = v 3 , $\varphi(v_1)=v_1$$\varphi(v_2)\in\{v_{36},v_2\}$$\varphi(v_2)=v_{36}$$\varphi(v_3)=v_{35}$$\varphi(v_4)$$\varphi(v_2)=v_2,\varphi(v_3)=v_3,\varphi(v_4)=v_4$$\varphi(v_5)\in\{v_3,v_5\}$$\varphi(v_5)=v_3$$\varphi(v_6)=v_4$$\varphi(v_7)$$\varphi$$v_1\to\ldots\to v_7$$D$. Secara khusus, tidak memetakan ke subgraph yang tepat.$\varphi$$D$