Wykresy sześcienne dzielące krawędzie na szpony i ścieżki

Znów problem podziału krawędzi, którego złożoność jestem ciekawy, motywowany moim poprzednim pytaniem .

Dane wejściowe: wykres sześcienny$G=(V,E)$

Pytanie: czy istnieje podział na , taki że podgrupa indukowana przez każdy jest albo pazurem (tj. , często nazywanym gwiazdą), albo ścieżką ( tj. )?E 1 , E 2 , … , E s E i K 1 , 3 3 P $E$$E_1, E_2, \ldots, E_s$$E_i$$K_{1,3}$$3$$P_4$

Wydaje mi się, że pewnego dnia widziałem artykuł, w którym okazało się, że ten problem jest NP-zupełny, ale nie mogę go już znaleźć i nie pamiętam, czy ten wynik dotyczy grafów sześciennych. W pokrewnej sprawie zdaję sobie sprawę, że dzielenie krawędzi dwuczęściowego grafu na szpony jest NP-zupełne (patrz Dyer i Fryz ). Czy ktoś ma odniesienie do problemu, który opisuję, lub czegoś związanego (tj. Ten sam problem na innej klasie grafów, który mógłbym następnie spróbować zredukować do wykresów sześciennych)?

To nie jest odpowiedź na złożoność problemu, ale przynajmniej pokazuje, że złożoność ma szansę być nietrywialna: to przykład sześciennego wykresu, którego nie można podzielić na ścieżki i pazury.

_{(źródło: uci.edu )}

W obrębie każdego z trzech płatów każdy podział na ścieżki i pazury może wykorzystywać tylko sześć z siedmiu krawędzi. Pozostałe sześć środkowych krawędzi ma postać pazura z każdą krawędzią podzieloną na części, których nie można podzielić na ścieżki i pazury.

ETA : Powyższy wykres jest bardziej znany jako przykład wykresu sześciennego bez idealnego dopasowania. Ale każdy sześcienny wykres z doskonałym dopasowaniem ma rozkład na ścieżki (nawet bez użycia pazurów). Według twierdzenia Königa obejmuje to wszystkie sześcienne dwuczęściowe wykresy, a według twierdzenia Petersena obejmuje wszystkie pozbawione mostów wykresy sześcienne, odpowiadając na pytanie Josepha Malkevitcha w komentarzach.

Dowód jest bardzo prosty: jeśli M jest idealnym dopasowaniem na wykresie sześciennym, usunięcie M pozostawia 2-regularny wykres, czyli rozłączny związek cykli. Ustaw każdy cykl dowolnie i dołącz każdą krawędź uv M do krawędzi cyklu, które następują u i v w orientacjach ich cykli.

W przeciwnym kierunku, jeśli istnieje rozkład na ścieżki, wówczas istnieje idealne dopasowanie: środkowe krawędzie każdej ścieżki muszą być dopasowane, ponieważ żadne dwie środkowe krawędzie nie mogą dzielić wierzchołka stopnia trzeciego.

(Zastrzeżenie: ten pomysł mógł być już obecny w zaproszonym przemówieniu Carstena Thomassena na GD 2010, który dotyczył tego rodzaju problemu rozkładu grafu).

(dodatek do zrzeczenia się odpowiedzialności (Anthony Labarre): „pomysł orientacji” dotyczący przejścia od idealnego dopasowania do partycji do ścieżek pojawia się w tym dokumencie Jünger, Reinelt i Pulleyblank , którzy przypisują to WH Cunninghamowi.)

Wygląda na to, że przegapiłem ten inny artykuł Dyera i Frieze'a , gdzie dowodzą oni, że podział krawędzi płaskiego dwuczęściowego grafu na połączone komponenty z krawędziami jest NP-zupełny dla każdego ustalonego (Twierdzenie 3.1 s. 145). Następnie komentują, że można wykazać, że problem pozostaje NP-zupełny dla jeśli wszystkie wierzchołki mają stopień lub , co chyba, że ​​nie przeanalizowałem tego w niewłaściwy sposób, obejmuje mój problem (ponieważ dane wejściowe są dwustronne, wykres nie zawiera dziwnych wartości cykl, a zwłaszcza brak trójkąta, co oznacza, że ​​jedynymi podgraphami, których możemy użyć, są pazury i ścieżki).k ≥ 3 k = 3 2 $k$$k\geq 3$$k=3$$2$$3$

To nie był właściwie koniec historii: jeśli wykres sześcienny jest dwustronny, to łatwo jest podzielić jego zestaw krawędzi za pomocą tylko pazurów, wybierając jeden zestaw dwuczęściowy i czyniąc go zestawem „centrów pazurów”. Ogólny problem jest rzeczywiście trudny, co można udowodnić, stosując redukcję SATYFIKOWALNOŚCI MONOTONE 1-IN-3 PLANARU PUBLICZNEGO. Wszystkie szczegóły są swobodnie dostępne na arxiv .

Być może ten artykuł może być interesujący:

Kleinschmidt, Peter Regularne partycje regularnych grafów. Canad Matematyka Byk. 21 (1978), no. 2, 177–181.

Zajmuje się wykresami, które można zapisać jako połączenie „ścieżek Z” o długości 3. (W szczególności płaskie, 3-walentne, 3-połączone wykresy-sześcienne 3-politopy).