Złożoność homomorfizmu digrafa w cyklu zorientowanym

Biorąc pod uwagę stałą skierowane wykres (digrafu) The -COLORING problem decyzyjny pyta czy digrafu wejście ma homomorfizm do . (Homomorfizmem od do jest odwzorowaniem od do , która chroni łuki, to znaczy, gdy jest łukiem , a jest łukiem )$D$$D$$G$$D$$G$$D$$f$$V(G)$$V(D)$$uv$$G$$f(u)f(v)$$D$

Klasa problemów COLORING jest silnie związana z hipotezą dychotomii dla CSP podaną przez Federa i Vardiego (dostępną na stronie cytowanej ).$D$

W tym 2001 papierze (dostępnym na stronie autora, tutaj ), Feder udowadnia twierdzenie dychotomii, gdy jest nastawiony na cykl (przez zorientowanego cyklu Znaczy undirected cykl gdzie każda krawędź jest zastąpione jednym łuku, które mogą być zorientowane dowolnie) , innymi słowy, pokazuje, że dla dowolnego zorientowanego cyklu , COLORING może być rozwiązany w czasie wielomianowym lub NP-zupełny.$D$$D$$D$

Niestety, klasyfikacja Federa jest wysoce nietrywialna i nieprecyzyjna, ponieważ złożoność wielu przypadków jest związana ze złożonością niektórych ograniczonych wariantów SAT, które zależą od orientacji. Patrząc na artykuł, nie byłem w stanie określić odpowiedzi na moje pytanie:

Pytanie: Jaki jest najmniejszy rozmiar zorientowanego cyklu tak że COLORING jest NP-zupełny?$D$$D$

Odpowiedź może być podana gdzieś w literaturze, ale nie mogłem jej znaleźć.

Edytować:Pozwól, że podam więcej szczegółów na temat klasyfikacji Federa. Feder pokazuje, że każdy zorientowany cykl NP musi być zrównoważony, to znaczy mieć taką samą liczbę łuków w obu kierunkach (stąd ma on nawet porządek). Następnie rozważ „poziomy” wywołane przez orientację (zacznij krążyć wokół cyklu na dowolnym wierzchołku; jeśli łuk idzie w prawo, idziesz w górę o 1, jeśli łuk idzie w lewo, idziesz w dół o 1). Następnie, jeśli istnieje co najwyżej jeden „przebieg od góry do dołu”, jest on wielomianowy. Jeśli są co najmniej 3 takie „przebiegi”, a cykl jest rdzeniem, oznacza to, że NP jest kompletny. (W przykładzie Andrasa z komentarzy istnieją trzy takie „przebiegi”, ale cykl nie jest rdzeniem.) Najtrudniejsze są przypadki z dwoma „przebiegami od góry do dołu”. Niektóre są trudne, inne wielomianowe, a Feder odnosi je do specjalnych problemów SAT w celu uzyskania dychotomii.

Jako pytanie pośrednie: jaki jest najmniejszy cykl, który ma trzy przebiegi „od góry do dołu” i jest rdzeniem? Taki przykład byłby NP-kompletny w powyższej dyskusji.

Co do pytania pośredniego (rdzeń z trzema przebiegami od góry do dołu)?

Trochę notacji: opiszę biegi słowami w $\{l,r\}^*$, z np $llrl$ odpowiadający subgraphowi $\cdot\leftarrow\cdot\leftarrow\cdot\to\cdot\leftarrow\cdot$. Poziom wzrasta dalej$r$ łuki i maleje $l$ łuki i zakładam, że jego minimum to $0$. Niektóre proste ograniczenia to:

• Nie może istnieć bieg składający się wyłącznie z $l$s lub tylko z $r$s, ponieważ w przeciwnym razie istnieje oczywisty homomorfizm z $D$ do tego przebiegu (mapowanie każdego węzła $D$do tego z tym samym poziomem). Oznacza to również, że maksymalny poziom musi wynosić co najmniej$3$.
• Jeśli maksymalny poziom to $3$, wówczas wszystkie przebiegi góra-dół (lub dół-góra) miałyby postać $llr(lr)^ill$ (odpowiednio. $rrl(rl)^irr)$; znowu nie jest trudno znaleźć homomorfizm$D$ do biegu, który minimalizuje $i$.

Jednak dla maksymalnego poziomu $4$ istnieje rozwiązanie długości $36$: rozważ $D$ podane przez $(rrrlrrlllrll)^3$. Ma to wymagane przebiegi od góry do dołu i jest rdzeniem (patrz poniżej). Zgodnie z powyższymi ograniczeniami jest to z konieczności minimalne, ponieważ każdy przebieg ma tylko jedną „tylną” krawędź.

Aby przekonać się, że jest to rdzeń, nazwijmy wierzchołki ($v_1,\ldots,v_{36}$). Dno (tj. Poziom$0$) wierzchołki są $v_1,v_{13},v_{25}$. Każdy homomorfizm$\varphi$ od $D$ do podgrafu musi zachować poziomy, w szczególności $\varphi(v_1)\in\{v_1,v_{13},v_{25}\}$; modulo oczywisty automorfizm$v_i\mapsto v_{i+12}$wystarczy rozważyć tę sprawę $\varphi(v_1)=v_1$. Rozważ sąsiedztwo$v_1$ w $D$ (z adnotacjami o poziomach):

$v_{34}(1)\to v_{35}(2)\leftarrow v_{36}(1)\leftarrow v_1(0)\to v_2(1)\to v_3(2)\to v_4(3)\leftarrow v_5(2)\to v_6(3)\to v_7(4)$

Począwszy od $\varphi(v_1)=v_1$, mamy $\varphi(v_2)\in\{v_{36},v_2\}$. Ale jeśli$\varphi(v_2)=v_{36}$, następnie $\varphi(v_3)=v_{35}$i nie mamy żadnej możliwej wartości $\varphi(v_4)$. Dostajemy$\varphi(v_2)=v_2,\varphi(v_3)=v_3,\varphi(v_4)=v_4$. Kolejny$\varphi(v_5)\in\{v_3,v_5\}$, ale dla $\varphi(v_5)=v_3$ dostajemy $\varphi(v_6)=v_4$, bez możliwej wartości dla $\varphi(v_7)$. Więc$\varphi$ musi być tożsamością podczas całego przebiegu $v_1\to\ldots\to v_7$i powtarzając ten sam argument dla pozostałych przebiegów, to samo dotyczy wszystkich $D$. W szczególności,$\varphi$ nie mapuje $D$ na odpowiedni wykres podrzędny.