Pencocokan maksimum M dengan kondisi G [M] bebas 2K_2

Apakah ada sesuatu dalam literatur yang dekat dengan masalah berikut:

Diberikan grafik bipartit dengan bipartisi seimbang { U , W } , apakah ada M yang cocok dengan sempurna di G sehingga untuk setiap 2 tepi u 1 w 1 , u 2 w 2 ∈ M , ada tepi u 1 w 2 atau tepi u 2 w 1 (atau keduanya) di G ?$G(V,E)$$\{U,W\}$$M$$G$$u_1w_1, u_2w_2\in M$$u_1w_2$$u_2w_1$$G$

Dengan kata lain, apakah ada pencocokan sempurna sehingga subgraf G [ M ] yang diinduksi adalah 2 K 2 -gratis. (Dengan bipartisi seimbang, maksud saya | U | = | W | .)$M$$G[M]$$2K_2$$|U|=|W|$

Kondisi tambahan adalah sesuatu seperti ekstrim berlawanan dari yang digunakan dalam masalah pencocokan yang diinduksi. Kemungkinan lain yang terkait adalah masalah menemukan pencocokan ukuran maksimum dalam grafik bipartit G sedemikian sehingga kontraksi tepi dalam M meminimalkan jumlah tepi yang tersisa dalam grafik.$M$$G$$M$

Saya memeriksa daftar masalah terkait pencocokan yang diberikan oleh Plummer di Matching dan vertex packing: seberapa "sulit" itu? tanpa keberhasilan.

PS: Masalah ini adalah kasus khusus dari masalah keputusan ini: - Untuk diberikan , apakah ada M maksimum yang cocok dari grafik bipartit G sehingga G [ M ] adalah 2 K 2 - bebas dan | M | > k . Jika grafik input seimbang bipartit dan k = | U | , kami mendapatkan masalah di atas.$k\in\mathbb{N}$$M$$G$$G[M]$$2K_2$$|M|>k$$k=|U|$

Terima kasih.

Mengherankan! (untuk saya).
Jenis pencocokan ini sudah dipelajari dalam literatur. Mereka disebut pencocokan terhubung .

Mereka diperkenalkan oleh Plummer, Stiebitz dan Toft dalam studi mereka tentang dugaan Hadwiger. Lihat bab "Pencocokan Terhubung" oleh Cameron dalam buku "Optimalisasi Gabungan - Eureka, You Shrink!"

Status pencocokan terhubung dalam grafik bipartit (tidak perlu seimbang) terbuka untuk yang terbaik dari pengetahuan saya ( saya akan memperbarui ). Versi tertimbang dari masalahnya adalah NP-lengkap untuk grafik bipartit. Masalahnya adalah waktu polinomial yang dapat dipecahkan untuk grafik bipartit chordal.

$n^{1-\epsilon}$

Catatan ditambahkan sebelumnya (disimpan untuk orang-orang yang tertarik):
" Pencocokan yang terhubung dalam grafik bipartit chordal " oleh Jobson et al. (doi: https://doi.org/10.1016/j.disopt.2014.06.003 ) dan " Pencocokan yang terhubung dalam kelompok grafik khusus " oleh Caragianis (tesis) adalah dua referensi penting.

$M$$G$$M$$G$
$e$$e’$$e$$e’$

$L(G)$$G$

Masalah set stong dikenal sebagai NP-complete di beberapa kelas grafik. Saya tidak tahu statusnya pada grafik garis grafik bipartit. Makalah itu mengatakan itu NP-lengkap pada grafik bipartit. Minat kami di sini akan berada di kelas grafik garis grafik bipartit.