Masalah "diarahkan" yang lebih mudah daripada varian "tidak diarahkan" mereka.

Saya sedang mempresentasikan kuliah tentang penyortiran pancake , dan menyebutkan bahwa:

• Mengurutkan berdasarkan pembalikan adalah NP-hard
• "ditandatangani" menyortir oleh pembalikan dalam P .

Yang membuat saya berpikir. Ada perasaan di mana penyortiran "tanda tangan" diarahkan "- Anda dapat melihat tanda sebagai arah (dan memang, inilah motivasi dari biologi evolusi). Tapi ini masalah yang lebih mudah! Ini tidak biasa karena umumnya (setidaknya pada grafik) masalah yang diarahkan lebih sulit (atau setidaknya sama sulitnya) dengan rekan-rekan mereka yang tidak terarah.

Dengan asumsi definisi "diarahkan" yang murah hati, apakah ada contoh masalah yang diarahkan yang lebih mudah daripada rekan-rekan mereka yang tidak diarahkan?

Menghitung sirkuit Euler untuk grafik berarah dapat dilakukan dalam waktu polinomial menggunakan teorema TERBAIK , sementara tampaknya, masalah yang sama untuk grafik tidak berarah adalah # P-complete .

Kasus yang menarik dan tidak begitu terkenal adalah sebagai berikut. Misalkan kita memiliki graf tepi-tertimbang dan simpul akar r . Kami ingin sub-grafik biaya-minimum G sedemikian sehingga ada jalur k edge-disjoint dari r ke setiap node dalam grafik. Ketika k = 1 ini adalah masalah arborescence min-biaya dalam grafik diarahkan dan dalam grafik tidak terarah itu setara dengan masalah MST. Keduanya dipecahkan dalam poli-waktu meskipun case yang tidak diarahkan lebih mudah. Namun masalahnya adalah waktu-terpecahkan dalam grafik terarah untuk setiap k sedangkan NP-Hard dalam grafik tidak terarah untuk k = 2 (karena ia menangkap biaya-min$G$$r$$G$$k$$r$$k=1$$k$$k=2$ masalah sub-grafik yang terhubung).$2$

Mungkin ini bukan contoh terbaik, tetapi pertimbangkan (Disutradarai) Cycle Cover, di mana tugasnya adalah untuk menutupi semua simpul dengan vertex-disjoint (diarahkan) siklus. Dalam kasus yang diarahkan, ini dapat direduksi menjadi pencocokan bipartit dan diselesaikan dalam waktu polinomial. Dalam kasus yang tidak diarahkan, masalahnya dapat direduksi menjadi pencocokan non-bipartit (dan sebaliknya), yang merupakan masalah yang lebih sulit, tetapi masih dapat dipecahkan dalam waktu polinomial.

Inilah masalah yang, seperti baru-baru ini saya sadari, terlihat lebih sulit dalam grafik yang tidak diarahkan daripada yang diarahkan.

$m\sqrt{n}\log C$$m$$n$$C$$n^3, mn\log n$

$m\sqrt{n}\log C$$n^3, mn\log n$