Czy przecięcie matroidów graficznych

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

Myślę, że nadal jest NP-kompletny, poprzez redukcję ścieżek hamiltonowskich na grafach dwudzielnych z dwoma wierzchołkami stopnia jeden i wszystkimi innymi wierzchołkami mającymi stopień trzeci. (Jest to tak samo jak znalezienie cykli hamiltonowskich przez określoną krawędź na sześciennym grafie dwustronnym - zastąp określoną krawędź dwoma liśćmi.)

Aby zredukować ze ścieżek hamiltonowskich do przecięcia matroidu graficznego, użyj jednego matroida graficznego, aby wymusić podgraph, który wybierzesz jako drzewo opinające (prawdziwe dla każdej ścieżki) i dwóch kolejnych matroidów graficznych, po jednej z każdej strony dwuczęściowej, aby wymusić subgraph mieć stopień dwa na każdym wierzchołku stopnia trzy i mieć krawędź na każdym wierzchołku stopnia jednego. Są to matroidy graficzne wykresu z rozłącznymi kopiami dla każdego wierzchołka stopnia 3 i K 2 dla każdego wierzchołka stopnia 1.$K_3$$K_2$

Co powiesz na wykorzystanie faktu, że dopasowanie 3-d jest NP kompletne, aby pokazać NP Kompletność tego problemu. Możemy łatwo napisać dopasowanie 3-d jako przecięcie 3 matroidów partycji, a matroid partycji to specjalny przypadek matroida graficznego (rozważ wykres z równoległymi krawędziami).