Di kelas grafik mana saja sumber daya dibatasi jalur terpendek (RCSP) NP-hard?

Saya ingin menghubungkan masalah yang sedang saya kerjakan dengan masalah NP-hard yang diketahui. Saya pikir saya bisa memodelkan masalah saya sebagai sumber daya masalah jalur terpendek yang dibatasi. Namun, struktur grafik saya tidak sepenuhnya arbitrer. Dengan demikian, akan berguna untuk mengetahui kapan RCSP menjadi sulit. Apakah sulit untuk DAG, untuk DAG planar, untuk DAG dengan derajat terikat? Bantuan apa pun akan sangat dihargai!

Saya tidak tahu apakah Anda masih tertarik dengan pertanyaan (lama) ini, dan jika saya memahami dengan baik kendala sumber daya yang Anda berikan dalam komentar; namun tampaknya masalah Anda (yang sedikit berbeda dari masalah RCSP biasa) adalah NP-complete untuk grafik planar (tidak diarahkan atau diarahkan atau diarahkan asiklik) dari max-degree 3 .

Pengurangan yang mudah adalah dari 3-SAT. Mengingat formula dengan n variabel x 1 , . . . x n dan m klausa C 1 , . . . C m :$\varphi$$n$$x_1,...x_n$$m$$C_1,...C_m$

• menambahkan kendala sumber daya set dengan dua simpul untuk setiap positif literal x k di φ dan kendala sumber daya set M - k dengan dua simpul untuk setiap negatif literal ˉ x k di φ ;$M_k^+$$x_k$$\varphi$$M_k^-$$\bar{x}_k$$\varphi$
• mulai membangun grafik dari node sumber dan untuk setiap variabel x i membagi jalan di dua jalur : satu atas melintasi satu titik dari semua M - k yang sesuai dengan negatif literal ˉ x k ; lebih rendah satu melintasi satu titik dari semua M + k yang sesuai dengan positif literal x k ;$s$$x_i$$M_k^-$$\bar{x}_k$$M_k^+$$x_k$
• maka untuk setiap membagi jalan dalam 3 baris yang melintasi secara paralel 3 simpul sesuai dengan literal dari C j dan yang dipetik dari yang sesuai M + k atau M - k ;$C_j$$C_j$$M_k^+$$M_k^-$
• akhirnya menambahkan simpul wastafel .$t$

Jalur dari ke t ada jika dan hanya jika rumus asli memuaskan (yaitu tanpa kehilangan generalitas Anda dapat meminta jalur panjang ≤ | V | ).$s$$t$$\leq |V|$

Secara informal ketika melintasi bagian variabel , jika Anda memilih garis atas ( penugasan benar ) maka Anda harus "menggunakan" salah satu simpul dari semua set kendala sumber daya M - k yang juga berisi titik yang dapat digunakan kemudian untuk melintasi (memuaskan) klausa yang mengandung ˉ x i . Jika Anda memilih garis bawah ( palsu tugas) maka Anda harus "menggunakan" salah satu simpul dari semua M + k sumber daya kendala set yang juga mengandung titik yang dapat digunakan kemudian untuk melintasi (memuaskan) klausul yang mengandung x $x_i$$M_k^-$$\bar{x}_i$$M_k^+$$x_i$. Ketika melintasi setiap klausul setidaknya salah satu dari tiga simpul harus terkandung dalam yang belum dapat "digunakan" belum (yaitu minimal salah satu dari mereka dapat digunakan untuk memenuhi klausa).$M_k$

Gambar berikut harus membuat pengurangan lebih jelas. Sumber daya kendala set diwakili dengan warna yang berbeda (dan untuk setiap warna ada tepat 2 simpul).$M_k$

$C_1 = x_1 \lor \bar{x}_2 \lor x_3$
$C_2 = x_2 \lor \bar{x}_3 \lor x_4$
$C_3 = \bar{x}_1 \lor x_3 \lor \bar{x}_2$

Anda juga dapat dengan mudah membuat grafik diarahkan, asiklik dan bipartit. Beri tahu saya jika Anda membutuhkan detail lebih lanjut (atau jika saya salah memahami masalahnya :-).

$k$