Hamiltoniczność wykresów k-regularnych

Wiadomo, że NP-kompletne jest sprawdzenie, czy cykl hamiltonowski istnieje na 3-regularnym wykresie, nawet jeśli jest on płaski (Garey, Johnson i Tarjan, SIAM J. Comput. 1976) lub dwustronny (Akiyama, Nishizeki, i Saito, J. Inform. Proc. 1980) lub w celu przetestowania, czy cykl hamiltonowski istnieje na wykresie 4-regularnym, nawet jeśli jest to wykres utworzony przez układ krzywych Jordana (Iwamoto i Toussaint, IPL 1994).

Dla którego innego k jest znany jako NP-kompletny do testowania Hamiltoniczności wykresów regularnych k?

Szczególnym przypadkiem, który mnie interesuje, są wykresy 6-regularne, z dodatkowym warunkiem, że wykres ma nieparzystą liczbę wierzchołków. Gdyby ten przypadek okazał się być kompletnym NP (lub wielomianowym), miałby wpływ na problem z rysowaniem wykresów opisany w http://arxiv.org/abs/1009.0579 . Warunek „nieparzystej liczby wierzchołków” polega na tym, że tak naprawdę chcę wiedzieć, w przypadku wykresów 6-regularnych, czy wykres zawiera albo cykl hamiltonowski, czy dwustronny 2-czynnikowy; ale posiadanie nieparzystej liczby wierzchołków eliminuje możliwość dwustronnego 2-czynnikowego, pozostawiając jedynie możliwość cyklu hamiltonowskiego.

Pierwszy krok zakłada, że ​​wykres ma parzystą liczbę wierzchołków. W drugim etapie rozszerzymy konstrukcję, aby jeśli k było parzyste, pokażemy, jak przekształcić wykres w nieparzystą liczbę wierzchołków.

Rozwiązaniem jest udoskonalenie pomysłu zasugerowanego w innej odpowiedzi.

Pierwsza część

Twierdzenie: Biorąc pod uwagę wykres $k$ nieregularny $G$ z parzystą liczbą wierzchołków, można obliczyć wykres $H$ który jest $(k+1)$ nieregularny, a $H$ oznacza hamiltonian iff$G$ oznacza hamiltonian.

$k$$G$$G_1$$G_2$$v \in V(G)$$v_1$$v_2$$k+2$$v$$v'$ w tej klice i usuń krawędź między nimi. Następnie podłącz v 1 do v ′ i v 2 do v ″ . Niech C ( v ) oznacza ten składnik dla v .$v''$$v_1$$v'$$v_2$$v''$$C(v)$$v$

Powtórz to dla wszystkich wierzchołków i niech H oznacza wynikowy wykres.$G$$H$

Oczywiście wykres jest k + 1 regularny. Twierdzimy, że H jest hamiltonianem tylko wtedy, gdy G jest hamiltonianem.$H$$k+1$$H$$G$

Jeden kierunek jest jasny. Biorąc pod uwagę Hambiltonian cykl w , możemy przetłumaczyć go w cyklu H . Rzeczywiście, ilekroć cykl odwiedza wierzchołek v , interpretujemy go jako przejście od v 1 do v 2 (lub odwrotnie) podczas odwiedzania wszystkich wierzchołków w C ( v ) . Jako taki, powoduje Hamiltona cyklu H . (Zauważ, że tutaj używamy faktu, że pierwotna liczba wierzchołków jest parzysta - jeśli cykl jest nieparzysty, to się psuje.)$G$$H$$v$$v_1$$v_2$$C(v)$$H$

Jeśli chodzi o drugą stronę, za cykl Hamiltona w . Musi być tak, że C ( v ) odwiedzana jest przez część cyklu, która rozpoczyna się w v 1 , odwiedza wszystkie wierzchołki C ( v ) i opuszcza z v 2 (lub opcja symetryczna). Rzeczywiście, cykl Hamiltona nie może wejść i wyjść z tego samego v i . Jako takie, Hamiltona w cyklu H jako naturalny interpretacji jako Hamiltona cyklu G . CO BYŁO DO OKAZANIA.$H$$C(v)$$v_1$$C(v)$$v_2$$v_i$$H$$G$

Druga część

Jak zauważono poniżej przez Tsuyoshi, każdy 3-regularny wykres ma parzystą liczbę wierzchołków. Jako taki problem jest trudny w przypadku wykresu nieregularnego z parzystą liczbą wierzchołków. Mianowicie, powyższa redukcja pokazuje, że problem jest trudny dla dowolnego wykresu k- regularnego, chociaż wykres wynikowy ma parzystą liczbę wierzchołków.$3$$k$

Zauważamy, że implikuje to, że następujący problem jest trudny NP.

Problem A: Decydując jeśli k-regularny graf o numerze nawet wierzchołków ma cykl Hamiltona przechodzący przez specyficzny krawędzi e .$G$$e$

Jeśli jednak otrzyma nawet instancję ( G , e ) , możemy zredukować ją do pożądanego problemu. Rzeczywiście, zastępujemy krawędź e kliką k + 1 wierzchołków, tak jak przed usunięciem jednej krawędzi kliki i połączeniem jej dwóch punktów końcowych z punktami końcowymi e i usunięciem e z wykresu. Oczywiście dla nowego wykresu H :$k$$(G, e)$$e$$k+1$$e$$e$$H$

• jest k- nieregularne.$H$$k$
• to hamiltonian iff G to hamiltonian z cyklem wykorzystującym e .$H$$G$$e$
• ma | V ( G ) | + k + 1 wierzchołków => H ma nieparzystą liczbę wierzchołków.$H$$|V(G)| + k+1$$H$

Zauważ, że nieregularny wykres, dla k nieparzystej, musi mieć parzystą liczbę wierzchołków (wystarczy policzyć krawędzie), jako taki, nie ma żadnych k- regularnych wykresów o nieparzystej liczbie wierzchołków, przy czym k jest nieparzyste.$k$$k$$k$$k$

Wynik

Trudno jest zdecydować, czy wykres nieregularny ma cykl hamiltonowski dla k ≥ 3 . Problem pozostaje trudny do rozwiązania, nawet jeśli wykres ma nieparzystą liczbę wierzchołków.$k$$k\geq 3$

Oczywiście, zawsze jest możliwe, że popełniłem głupi błąd ...

Ćwiczenie

Jeśli chcemy przejść z wykresu, który jest nieregularny, do wykresu, który jest (powiedzmy) 2 k- nieregularny, wówczas wykres wynikający z zastosowania powyższej redukcji wielokrotnie daje wykres o wielkości zależnej wykładniczo od k . Pokazują, że biorąc pod uwagę K -regular wykres G i I > 2 , można sporządzić wykres H , która jest ( k + I ) -regular i jego rozmiar jest wielomianem k , I i n , gdzie n jest liczbą wierzchołków o G . Ponadto,$k$$2k$$k$$k$$G$$i >2$$H$$(k+i)$$k,i$$n$$n$$G$ jest hamiltonianem wtedy i tylko wtedy, gdy H jest hamiltonianem.$G$$H$

(Publikuję to jako ćwiczenie, a nie pytanie, ponieważ wiem, jak to rozwiązać).

EDYCJA: Ten dowód jest błędny, jak wskazano w komentarzach. (Czy powinienem usunąć post?)

Intuicyjnie wydaje się, że jeśli Hamiltonicity jest trudna dla NP dla wykresów regularnych k, to powinna być również trudna dla NP dla wykresów regularnych (k + 1). Oto redukcja z tyłu koperty, która dla mnie wygląda dobrze, ale oczywiście może wystąpić błąd.

Niech G będzie k-regularnym wykresem. Niech G będzie graficznym iloczynem kartezjańskim G i krawędzi. Innymi słowy, G 'jest wykresem zawierającym dwie kopie G, a każdy wierzchołek jest połączony z jego kopią. G 'jest teraz (k + 1) regularne, ponieważ każdy wierzchołek ma 1 dodatkową krawędź.

Twierdzenie: G ma cykl hamiltonowski, tylko wtedy, gdy G 'ma cykl hamiltonowski.

Dowód: jeśli G ma cykl hamiltonowski, łatwo zauważyć, że G 'również go ma. Powiedz (u, v) jest krawędzią w cyklu hamiltonowskim. Przejdź przez cykl od u do v bez użycia tej krawędzi, a teraz zamiast używać krawędzi, przejdź do v 'od v, gdzie v' jest wierzchołkiem odpowiadającym v w kopii G. Teraz przejdź przez cykl w odwrotnej kolejności na tym wykresie, który przywróci nas do ciebie. Teraz przejdź od u 'do u, co kończy cykl.

Jeśli G 'ma cykl hamiltonowski rozpoczynający się od wierzchołka u, rozważ tę samą sekwencję przechodzenia na G. Za każdym razem, gdy ruch jest wykonywany na sąsiednim wierzchołku na tym samym wykresie, wykonujemy ten sam ruch w G. Za każdym razem, gdy ruch jest wykonywany do odpowiedniego wierzchołka na drugim wykresie nic nie robimy. Ponieważ każdy ruch jest prawidłowy na wykresie G, a cykl kończy się na wierzchołku u, jest to cykl hamiltonowski.