Minimum spanning tree atas semua pencocokan titik

Saya mengalami masalah pencocokan ini yang saya tidak dapat menuliskan algoritma waktu polinomial.

Biarkan menjadi grafik tertimbang lengkap dengan masing-masing set vertex dan , di mana . Juga, biarkan dan menjadi fungsi bobot masing-masing di tepi danP V Q $P, Q$$P_V$$Q_V$$|P_V| = |Q_V|=n$$w_P$$w_Q$$P$$Q$

Untuk bijih kami memodifikasi dengan cara berikut: Jika dan dengan lalu atur . grafik yang dimodifikasi ini oleh dan biarkan menjadi jumlah bobot pohon rentang minimum . Q f ( p ) = q f ( p ′ ) = q ′ w P ( p , p ′ ) > w Q ( q , q ′ ) w Q ( q , q ′ ) = w P ( p , p ′ ) Q f W ( $f: P_V \to Q_V$$Q$$f(p) = q$$f(p^\prime) = q^\prime$$w_P(p, p^\prime) > w_Q(q, q^\prime)$$w_Q(q, q^\prime) = w_P(p, p^\prime)$$Q_f$Q $W(Q_f)$$Q_f$

Masalah: Minimalkan pada semua bijections .f : P V → Q $W(Q_f)$$f: P_V \to Q_V$

Seberapa sulit masalah ini? Jika "keras": bagaimana dengan algoritme aproksimasi?

(Pindah dari komentar) Berikut adalah ide untuk mendapatkan perkiraan faktor konstan, dengan asumsi P dan Q memenuhi ketimpangan segitiga. Saya pikir itu mungkin memberikan 2-aproksimasi, tapi yang bisa saya buktikan saat ini adalah rasio aproksimasi 4.

(1) Dalam masalah seperti yang dinyatakan, bobot tepi dalam grafik gabungan (setelah korespondensi - dan - ditentukan) adalah . Sebagai gantinya, mari kita gunakan . Ini kehilangan paling banyak faktor dua tetapi membuat masalah lebih mudah untuk dijelaskan: kita sekarang mencoba untuk menemukan pohon spanning di , dan pohon spanning isomorfik di , dengan berat total minimum. Korespondensi antara dan kemudian diberikan oleh isomorfisme antara kedua pohon ini.p p ′ q q ′ maks { P ( p q ) , Q ( p ′ q ′ ) } P ( p q ) + Q ( p ′ q ′ ) P Q P $pq$$p$$p'$$q$$q'$$\max\{P(pq),Q(p'q')\}$$P(pq)+Q(p'q')$$P$$Q$$P$$Q$

(2) Dalam , temukan pohon rentang minimum, dan gunakan teknik tur jalur pengganda jalan untuk menemukan jalur dengan paling banyak dua kali berat. Lakukan hal yang sama secara independen di . Hasilnya adalah dua pohon isomorfik (kedua jalur) yang terpisah secara terpisah paling banyak dua kali lipat berat MST grafiknya, dan karenanya paling banyak dua kali lipat biaya solusi untuk masalah pohon rentang isomorfik minimum, dan empat kali lebih berat dari masalah aslinya. .$P$$Q$

(3) Masalah aslinya adalah NP-lengkap, dengan pengurangan dari jalur Hamiltonian. Biarkan didefinisikan dari grafik di mana Anda ingin menguji keberadaan jalur Hamilton; define saat adalah edge pada dan saat bukan edge. Biarkan didefinisikan dengan cara yang persis sama dari grafik jalur. Lalu ada solusi dari total biaya jika dan hanya jika grafik dari mana didefinisikan memiliki jalur Hamiltonian. Mungkin ini juga dapat digunakan untuk membuktikan ketidak-taksiranan di bawah beberapa konstanta tetap.$P$$P(pq)=1$$pq$$P$$2$$pq$$Q$$n-1$$P$