Kompleksitas penghitungan pencocokan dalam grafik bipartit

Saya mungkin kehilangan sesuatu yang jelas tetapi saya tidak dapat menemukan referensi tentang kompleksitas penghitungan pencocokan (bukan pencocokan sempurna) dalam grafik bipartit. Inilah masalah formal:

Input: grafik bipartit dengan $G = (U, V, E)$ $E \subseteq U \times V$
Output: jumlah matchings dari , di mana matchings adalah bagian sehingga tidak ada yang terjadi di dua tepi . $G$ $F \subseteq E$ $v \in U \sqcup V$ $F$

Apa kompleksitas masalah ini? Apakah itu # P-keras?

Sudah diketahui bahwa menghitung kecocokan sempurna pada grafik bipartit adalah # P-hard, dan diketahui bahwa menghitung kecocokan grafik sewenang - wenang (atau bahkan grafik 3-reguler planar) adalah # P-keras oleh makalah ini , tetapi saya tidak t menemukan sesuatu tentang penghitungan kecocokan tidak sempurna pada grafik bipartit.

counting-complexity matching bipartite-graphs a3nm
sumber

Tampaknya ada masalah dalam algoritme ini. Ada beberapa kasus dalam hasil di mana tidak semua node dari sisi kiri atau kanan dimasukkan dalam solusi 2sat sehingga algoritma penghitungan yang tepat tidak berfungsi. Apakah ada yang tahu algoritma untuk solusi pencocokan bipartit maksimum tunggal yang diturunkan menggunakan pengurangan menjadi 2sat?

user3700810

Satu minggu di kelas teori kompleksitas saya di perguruan tinggi, masalah pekerjaan rumah kami satu-satunya adalah untuk membuktikan bahwa # 2-SAT adalah # P-lengkap, dengan mengurangi dari #BIPARTITE PERFECT MATCHING. Tidak ada yang bisa menyelesaikannya, bahkan ketika kita semua akhirnya bersatu untuk mengerjakannya.

Kelas berikutnya, profesor terkejut melihat betapa sulitnya kita semua menemukannya dan memberikan buktinya. Itu salah. Untungnya, satu cookie pintar mampu memberikan pengurangan yang benar, yang benar-benar gila dan rumit menjijikkan. Ngomong-ngomong, profesor memiliki Penghargaan Turing :)

Ngomong-ngomong, sementara saya dan teman-teman sekelas saya tidak bisa menyelesaikan masalah itu, kami dapat memecahkan masalah yang lebih mudah yaitu dari #BIPARTITE MATCHING menjadi # 2-SAT, jadi inilah bukti yang saya buat beberapa tahun yang lalu.

Dalil. #BIPARTITE MENCOCOK # 2-SAT. $≤_p$

Bukti . Biarkan menjadi turunan dari #BIPARTITE MATCHING. Biarkan set partisi menjadi (jadi dan ) . $G = (V,E)$

A = {a_{i} ∣ i \in [n]}, B = {b_{i} ∣ i \in [m]}

$A = \{a_i \mid i∈[n]\}, \quad B = \{b_i \mid i∈[m]\}$

| A | = n

$|A|=n$

| B | = m

$|B|=m$

Sekarang kita mengurangi menjadi rumus 2SAT , sehingga setiap penugasan yang memuaskan adalah kecocokan , dan sebaliknya. Untuk memulai, untuk setiap sisi membuat variabel . Idenya adalah bahwa menyetel variabel ke TRUE sesuai dengan edge berada dalam pencocokan. Untuk setiap simpul , buat ekspresi 2SAT Agar dipenuhi, semua kecuali satu dari harus salah. Untuk melihat ini, asumsikan keduanya $G$ $φ$ $φ$ $G$ $a_ib_j ∈ E$ $x_{ij}$ $x_{ij}$ $a_ib_j$ $i$

A_{i} = \underset{j < k}{⋀} (\neg x_{i j} \lor \neg x_{i k}), B_{i} := \underset{j < k}{⋀} (\neg x_{j i} \lor \neg x_{k i})

$A_i = \bigwedge_{j < k} (¬x_{ij} ∨ ¬x_{ik}), \quad B_i := \bigwedge_{j<k} (¬x_{ji} ∨ ¬x_{ki})$

A_{i}

$A_i$

x_{i j}

$x_{ij}$

x_{i j}

$x_{ij}$ dan benar. Maka salah, dan begitu juga . Hal yang sama berlaku untuk . Membiarkan kita memiliki yang puas jika dan hanya jika setiap simpul dalam adalah insiden paling banyak satu sisi yang kita pilih, dan dengan demikian ujung-ujungnya membentuk pencocokan.

x_{i k}

$x_{ik}$

(\neg x_{i j} \lor \neg x_{i k})

$(¬x_{ij} ∨ ¬x_{ik})$

A_{i}

$A_i$

B_{i}

$B_i$

C = ⋀_{i = 1}^{n} A_{i} \land ⋀_{i = 1}^{m} B_{i}

$C = \bigwedge_{i=1}^n A_i ∧ \bigwedge_{i=1}^m B_i$

C

$C$

G

$G$

kepala kebun
sumber

Saya pikir saya pasti kehilangan sesuatu di sini. Tampaknya ini menunjukkan bahwa turunan #BIPARTITE_MATCHING yang sewenang-wenang dapat disandikan sebagai turunan dari # 2-SAT. Tapi, saya berharap Anda akan mencoba untuk menunjukkan bahwa turunan # 2-SAT yang sewenang-wenang dapat dikodekan sebagai turunan dari #BIPARTITE_MATCHING, bukan?

mhum

Aduh, kau benar. Ini diambil dari masalah pekerjaan rumah lama dan saya tidak benar-benar memiliki pertanyaan yang ditulis, hanya jawaban saya. Masalahnya pasti menunjukkan bahwa # 2-SAT adalah # P-Complete, mengetahui bahwa # BIPARTITE-PERFECT-MATCHING adalah # P-complete. Saya akan mengeditnya.

Gardenhead

@ardenarden: Terima kasih atas jawaban Anda! Ini menarik tetapi saya tidak berpikir ini sangat terkait dengan pertanyaan saya, bukan? Ini hanya menunjukkan bahwa # BIPARTITE-MATCHING ada di #P, yang tidak terlalu mengejutkan.

a3nm

Pengurangan jawaban ini tampaknya benar, meskipun tampaknya tidak ada hubungannya dengan pertanyaan. Namun, saya tidak mengerti komentar @3nm, saya juga tidak mengikuti cerita di kata pengantar dari jawaban (yang agak membingungkan tiga pengurangan berbeda).

András Salamon

Saya menemukan cara mengurangi # MONO-2SAT menjadi #BIPARTITE PERFECT MATCHING, tapi buktinya tidak sesederhana itu: P.

Kompleksitas penghitungan pencocokan dalam grafik bipartit

Jawaban: