Apakah persimpangan

16

Diketahui bahwa persimpangan dari tiga matroid umum adalah NP-hard ( sumber ), yang dilakukan melalui reduksi dari siklus Hamiltonian. Pengurangan menggunakan satu matroid grafis dan dua matroid konektivitas.

Kasus khusus dari masalah yang sedang saya kerjakan dapat diselesaikan dengan persimpangan beberapa matroid grafis, tetapi saya belum dapat menemukan, apakah masalah ini ada di P.

Pertanyaan: Apakah diketahui? Bisakah seseorang merujuk saya ke kertas atau sesuatu?

( Catatan: Saya telah mengajukan pertanyaan ini tentang Ilmu Komputer dan dirujuk di sini.)

Matej Konecny
sumber

Jawaban:

11

Saya pikir itu masih NP-lengkap, dengan pengurangan dari jalur Hamiltonian dalam grafik bipartit dengan dua simpul derajat satu dan semua simpul lainnya memiliki derajat tiga. (Ini sama dengan menemukan siklus Hamilton melalui tepi yang ditentukan dalam grafik bipartit kubik - ganti tepi yang ditentukan dengan dua daun.)

K3K2

David Eppstein
sumber
8

Bagaimana kalau menggunakan fakta bahwa 3-d matching adalah NP lengkap untuk menunjukkan NP Completeness dari masalah ini. Kita dapat dengan mudah menulis pencocokan 3-d sebagai perpotongan dari 3 matroid partisi, dan matroid partisi adalah kasus khusus dari matroid grafis (pertimbangkan grafik dengan tepi paralel).

Sahil Singla
sumber
3
Tidak benar bahwa matroid partisi selalu merupakan matroid grafis, tetapi dalam kasus Anda, Anda ingin memilih tepat satu elemen dari setiap bagian, dan matroid itu grafis.
Sasho Nikolov