Mengarahkan masalah NP-hard pada DAG

Lebar pohon mengukur seberapa dekat grafik dengan pohon. Beberapa masalah NP-hard dapat dilakukan pada grafik dengan lebar pohon yang dibatasi. Jika masalah tetap NP-keras pada pohon maka lebar pohon tidak dapat menyelamatkan kita. Ini adalah motivasi di balik salah satu pertanyaan saya sebelumnya yang menanyakan masalah NP-hard pada pohon.

Ada beberapa versi lebar pohon terarah yang mengukur seberapa dekat grafik berarah dengan graf asiklik terarah (DAG). Apa saja masalah yang diarahkan yang tetap NP-keras pada DAG? Masalah terarah membuat penggunaan penting dari arah tepi. Misalnya, jalur hamiltonian adalah masalah terarah sedangkan vertex cover tidak. Salah satu jawaban untuk pertanyaan saya sebelumnya memberikan resep umum untuk menghasilkan masalah yang sulit pada pohon. Apakah ada resep untuk DAG?

Ini hanya bertujuan sebagian menjawab pertanyaan pertama dari pos:

Apa saja masalah yang diarahkan yang tetap NP-keras pada DAG?

Dalam [1], beberapa masalah alami pada grafik diarahkan diberikan yang tetap NP-keras pada DAG. Motivasi dari makalah ini adalah untuk menemukan ukuran seperti "treewidth" yang bagus untuk digraf. Mereka berpendapat bahwa kelemahan dari banyak langkah untuk digraf adalah bahwa mereka konstan untuk DAG, tetapi banyak rekan-rekan yang diarahkan dari masalah alam tetap NP-keras pada DAG. Untuk lebih lanjut tentang topik ini, lihat juga [2] dan referensi dari makalah ini.

[1] Robert Ganian, Petr Hlinený, Joachim Kneis, Alexander Langer, Jan Obdrzálek, Peter Rossmanith: Pada Ukuran Lebar Digraph dalam Algoritma Parameter. IWPEC 2009: 185-197. Versi lengkap

[2] Robert Ganian, Petr Hlinený, Joachim Kneis, Daniel Meister, Jan Obdrzálek, Peter Rossmanith, Somnath Sikdar: Apakah ada ukuran lebar digraf yang bagus ?. IPEC 2010, muncul. arXiv

Beberapa masalah routing diketahui NP-hard dan bahkan sulit untuk mendekati faktor polinomial dalam DAG. Ini termasuk masalah-masalah seperti jalur ujung-disjoint maksimum dan minimalisasi kemacetan. Lihatlah kertas-kertas karya Andrews, Chuzhoy, Khanna, Zhang dan lainnya untuk petunjuk lebih lanjut.

Dari sudut pandang logika, mengevaluasi formula MSO adalah NP-keras pada DAG. Misalnya, mengatakan grafik G dapat berwarna 3. Dan untuk setiap graf tidak diarahkan , kita dapat mengarahkan tepinya untuk mendapatkan DAG , dan mengubah semua dalam menjadi . Sekarang kita memiliki .$\varphi:=\exists C_1 C_2 C_3 [\forall x (C_1 x \lor C_2 x \lor C_3 x) \land \bigwedge_{i=1,2,3}\forall x,y(\neg C_i x \lor \neg C_i y\lor \neg E(x,y))]$$G$ E ( x , y ) φ E ( x , y ) ∨ E ( y , x ) G ⊨ $G'$$E(x,y)$$\varphi$$E(x,y)\lor E(y,x)$$G\models\varphi\iff G'\models\varphi'$

Masalah OPEN [8] yang terkenal dari daftar Garey dan Johnson berada di luar P, tetapi terbuka untuk dibuktikan sebagai NP-C. Masalahnya ada di DAG. Setiap putaran Anda dapat menghapus paling banyak tiga simpul yang tidak memiliki tepi masuk. Putuskan apakah semua simpul DAG dapat dihapus dalam putaran K? BUKA dari tahun 1970-an.