Isomorfisme subgraph yang tidak sempurna

Pertimbangkan masalah berikut: Diberikan grafik kueri $G = (V, E)$ dan grafik referensi , kami ingin menemukan pemetaan injeksi yang meminimalkan jumlah ujung-ujungnya ( v 1 , v 2 ) ∈ E sedemikian sehingga ( f ( v 1 ) , f ( v 2 ) ) ∉ E ′ . Ini adalah generalisasi dari masalah isomorfisme subgraphf : V → V $G' = (V', E')$$f : V \rightarrow V'$$(v_1, v_2) \in E$$(f(v_1), f(v_2)) \notin E'$di mana kita membiarkan subgraf menjadi isomorfik hingga beberapa tepi yang hilang dan ingin menemukan cara untuk meminimalkan jumlah tepi yang hilang.

$(v_1, v_2) \in V^2$$w(v_1, v_2)$$(v_1, v_2) \notin E)$$G'$$\sum_{v_1, v_2} (\max(0, w(v_1, v_2) - w(f(v_1), f(v_2))))$$\max$ ada untuk hanya menghukum bobot dari grafik kueri yang lebih besar dari pada grafik referensi).

Pertanyaan saya adalah: Apakah masalah ini sudah dipelajari? Apakah itu memiliki nama yang terkenal? Apakah ada algoritma perkiraan yang diketahui efisien?

Motivasi dari masalah ini (terlepas dari kenyataan bahwa itu tampak seperti generalisasi alami dari masalah isomorfisme subgraph) adalah bahwa itu adalah cara yang bagus untuk membuat rencana tabel untuk pesta: grafik kueri adalah grafik tamu dengan bobot tepi mewakili sejauh mana dua orang ingin berinteraksi, grafik referensi memiliki kursi meja sebagai simpul dan bobot tepi menunjukkan sejauh mana komunikasi dimungkinkan, solusi dari masalah adalah pemetaan dari orang ke kursi meja yang menghormati struktur sosial untuk sejauh mungkin.

Masalah Anda adalah Maksimum Common Edge Subgraph Problem (Max CES) yang didefinisikan sebagai berikut: diberi dua grafik dan G ′ , cari grafik H dengan jumlah ujung maksimum yang isomorfik ke subgraf G dan ke subgraf G ′ .$G$$G'$$H$$G$$G'$

Bukti : Anda menemukan subgraf dari G isomorfik ke subgraf G ′ , di mana | E G | - | E H | diminimalkan. Sejak | E G | adalah invarian dari G , | E G | - | E H | diminimalkan jika dan hanya jika | E H | dimaksimalkan. Jelaslah, H isomorfis untuk subgraf G dan subgraf $H$$G$$G'$$|E_{G}| - |E_{H}|$$|E_{G}|$$G$$|E_{G}| - |E_{H}|$$|E_{H}|$$H$$G$ . QED$G'$

Aproksimasi. Dalam tesis Ph.D dari Kann, saya menemukan deskripsi "tidak diketahui dapat diperkirakan dalam konstanta" [3] (hal. 115). Dalam makalah baru-baru ini oleh Bahiense et al. [1], disebutkan bahwa jika dan | V G ′ | tidak harus sama, masalahnya menjadi APX-keras. Tetapi kutipan untuk hasil ini adalah komunikasi pribadi yang tidak dipublikasikan [2].$|V_{G}|$$|V_{G'}|$

1. L. Bahiense, G. Manic, B. Piva, CC de Souza. Masalah subgraph tepi umum maksimum: Investigasi polihedral. Matematika Terapan Diskrit, untuk muncul. doi: 10.1016 / j.dam.2012.01.026
2. MM Halldorsson, Komunikasi pribadi, naskah yang tidak diterbitkan, 1994.
3. V. Kann. Tentang Perkiraan Masalah Optimalisasi NP-lengkap. Ph.D. Tesis, laporan NADA TRITA-NA-9206, 1992. http://www.nada.kth.se/~viggo/papers/phdthesis.pdf