Tambahkan pencocokan ke jalur Hamiltonian untuk mengurangi jarak maksimum antara pasangan simpul yang diberikan

Apa kompleksitas dari masalah berikut ini?

Masukan :

• $H$ a jalur Hamilton di$K_n$
• $R \subseteq [n]^2$ subset pasangan simpul
• bilangan bulat positif$k$

Pertanyaan : apakah ada cocok sehingga untuk setiap , ? (di mana )( v , u ) ∈ $M$$(v,u) \in R$$d_G(v,u) \leq k$
$G = ([n], M\cup H)$

Saya telah berdiskusi dengan seorang teman tentang masalah ini. Teman saya berpikir masalahnya ada di waktu polinomial. Saya pikir itu NP-lengkap.

Jawaban ini salah .

Temanmu benar. Masalah Anda (seperti yang ditafsirkan oleh Sasho) tidak menempatkan batasan apapun pada kardinalitas pencocokan . Oleh karena itu, memilih C menjadi pencocokan antara pasangan dalam R . Kemudian untuk bilangan bulat positif k , jarak antara setiap pasangan dalam R kurang dari k .$C$$C$$R$$k$$R$$k$

Masalah Anda menjadi menarik jika Anda memaksa jalur mengandung tepi dari kedua pencocokan dan jalur P .$C$$P$

UPDATE: jawaban di bawah ini tidak benar, karena saya salah berasumsi bahwa jalur Hamilton adalah dalam grafik arbitrer, bukan dalam . Saya membiarkannya tidak terhapus, mungkin saya akan bisa memperbaikinya atau itu akan memberikan beberapa petunjuk untuk jawaban lain.$K_n$

Saya pikir ini NP-lengkap. Ini adalah ide pengurangan yang sangat informal / cepat dari 3SAT

Untuk setiap variabel tambahkan "gadget variabel" dengan:$x_i$

• tiga node $X_i, +X_i, -X_i$
• dua tepi variabel dan ( X i , - X i$(X_i,+X_i)$$(X_i,-X_i)$

Tambahkan node sumber dan hubungkan ke semua variabel X i .$S$$X_i$

Untuk setiap klausul menambahkan node C j dan menghubungkannya dengan variabel yang sesuai + X i atau - X i bahwa bentuk klausa.$C_j$$C_j$$+X_i$$-X_i$

Gambar berikut menunjukkan: $(+x_1 \lor -x_2 \lor -x_3) \land (-x_2 \lor x_3 \lor x_4)$

Set (node yang harus dihubungkan) mengandung ( S , C 1 ) , ( S , C 2 ) , . . $R$$(S, C_1), (S,C_2), ...$

Jalur sederhana harus mencakup semua tepi "BIRU" kecuali tepi variabel ( X i , + X i ) dan ( X i , - X i ) (pada gambar di atas tepi biru mewakili tepi yang kami sertakan dalam P ).$P$$(X_i, +X_i)$$(X_i, -X_i)$$P$

Pada titik ini, rumus awal adalah satisfiable jika dan hanya jika jalur terpendek dari ke setiap klausul simpul C j tidak lebih besar dari tiga. Memang untuk mencapai klausa dari S dalam tiga langkah, kita harus melintasi setidaknya satu variabel X i : S → X i → ± X i → C j . Jadi kita harus melintasi salah satu dari dua tepi: X i → + X i atau X i → - X i ) dan memasukkannya ke dalam $S$$C_j$$S$$X_i$$S \to X_i \to \pm X_i \to C_j$$X_i \to +X_i$$X_i \to -X_i)$$C$(karena dengan konstruksi itu bukan bagian dari ). Tetapi keduanya tidak dapat dimasukkan, karena mereka berbagi titik.$P$

Tetapi kami tidak yakin bahwa kami dapat membangun jalur P sederhana yang mencakup semua tepi biru karena beberapa node memiliki lebih dari satu insiden tepi biru.$P$

Untuk memperbaikinya, kami mengganti setiap node dengan beberapa tepi biru insiden, dengan pohon yang hanya berisi pasangan tepi biru insiden yang akan dimasukkan dalam dan tepi yang memisahkannya dan yang harus disertakan dalam C untuk mencapai node klausa:$P$$C$

Grafik asli menjadi:

$K$$C_j$$S$

$C$

$P$