Wiadomo, że przecięcie trzech ogólnych matroidów jest NP-twarde ( źródło ), co odbywa się poprzez redukcję z cyklu Hamiltona. Redukcja wykorzystuje jedną matroidę graficzną i dwie matroidy łączności.
Specjalny przypadek problemu, nad którym pracuję, można rozwiązać, przecinając wiele matroidów graficznych, ale nie udało mi się ustalić, czy problem występuje w P.
Pytanie: czy to jest znane? Czy ktoś może polecić mi artykuł lub coś takiego?
( Uwaga: zadałem to pytanie na temat informatyki i zostałem tutaj przekazany).
źródło