Czy przecięcie matroidów graficznych

16

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

Matej Konecny
źródło

Odpowiedzi:

11

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)

David Eppstein
źródło
8

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

Sahil Singla
źródło
3
Nie jest prawdą, że matroid partycji jest zawsze matroidem graficznym, ale w twoim przypadku chcesz wybrać dokładnie jeden element z każdej części, a matroid to grafika.
Sasho Nikolov