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.)
sumber