Najdłuższy cykl zawarty w dwóch cyklach

Czy następujący problem NP-jest kompletny? (Zakładam, że tak).

Wprowadź: niekierowany wykres, na którym zbiór zboczy może zostać rozłożony na dwa proste cykle rozłączne od krawędzi ( nie są one częścią danych wejściowych). $k \in \mathbb{N},G=(V,E)$

Pytanie: Czy istnieje prosty cykl w o długości większej niż ? $G$ $k$

Oczywiście problem dotyczy NP, a maksymalny stopień w wynosi , ale to nie wydaje się pomocne. $G$ $\leq 4$

graph-theory np-complete decision-problem

— Wymienianie kolejno
źródło

Nie sądzę, że masz rację co do „najwyżej 4 ścieżek łączących dowolną parę”. Patrz: i.imgur.com/mYL4n1V.png

— svinja

@svinja Masz rację, powinienem był powiedzieć, że pomiędzy dowolną parą dwóch wierzchołków istnieją co najwyżej 4 pary rozłącznych krawędzi.

— Wpis

Twój tytuł wprowadza w błąd, ponieważ najdłuższy prosty cykl nie może być żadnym z dwóch cykli w rozkładzie (w dowolnym rozkładzie).

E

$E$

— Denis

@dkuper potrafi, spójrz na połączenie dwóch rozłącznych prostych cykli wierzchołków.

— Wpis

Nie chodzi mi o to, że nigdy nie może być jednym z nich, lecz o to, że czasami nie jest jednym z nich. Problemem nie jest znalezienie większego z nich.

— Denis

Odpowiedzi:

Próba redukcji ....

Redukcja ze ścieżki hamiltonowskiej na wykresie z maksymalnym stopniem 3, którym jest NPC [G&J] $G = (V,E)$

zignoruj kierunek krawędzi i przy użyciu pierwszego skanowania głębokości (niekierowanego) z dowolnego węzła podziel krawędzie na dwa zestawy odrębnych (niekierowanych) ścieżek (czerwony i zielony na rysunkach); $G$
połącz czerwone ścieżki, dodając dodatkowe „węzły łączące” (fioletowe węzły na rysunku B) i zrób niekierowany czerwony obwód; połącz zielone ścieżki, dodając dodatkowe „węzły łączące” (fioletowe węzły na rysunku) i stwórz niekierowany zielony obwód;
transformuj każdy pierwotny węzeł stopnia 1 i przewyższający 2 (rysunek C), dodając żółtych węzłów na przychodzącej czerwonej krawędzi i dodając żółtych węzłów na pierwszej wychodzącej czerwonej krawędzi ; na koniec dodaj żółtych węzłów „w kierunku” drugiej wychodzącej zielonej krawędzi używając „owiniętej” ścieżki wokół która dotyka najbardziej zewnętrznych żółtych węzłów czerwonych krawędzi (rysunek D). $b \in V$ $k$ $a\to b$ $k$ $b \to c$ $k$ $b \to d$ $b$

Na wynikowym wykresie wszystkie żółte węzły można pokonywać prostą ścieżką tylko na dwa sposoby pokazane na rysunku E i rysunku F, które odpowiadają dwóm prawidłowym przemianom pierwotnego węzła ; nieformalnie, jeśli używana jest krawędź w kierunku dodatkowego „łączącego” fioletowego węzła, żółtych węzłów nie można przejść. $3k$ $b \in V$ $k$

transformuj każdy oryginalny węzeł V stopnia 2 i stopnia 1 w podobny sposób

Wybór wystarczająco dużego, wykres wynikowy ma prostą ścieżkę o długości większej niż wtedy i tylko wtedy, gdy oryginalny wykres ma ścieżkę hamiltonowską (o długości ) $k \gg |V|$ $G'$ $3k(|V|-1)$ $G$ $|V|-1$

wprowadź opis zdjęcia tutaj

Większy obraz można pobrać tutaj

— Vor
źródło

To bardzo piękny dowód, być może powinieneś skierować krawędzie na rysunku „A”, aby ułatwić zrozumienie, jak uzyskać ścieżki (myślę, że to zrozumiałem).

— Wpis

@Listing: konstrukcja ścieżek nie zależy od ukierunkowanych krawędzi (w odpowiedzi napisałem wyszukiwanie „bezkierunkowe”). Powinieneś zacząć od dowolnego węzła, najpierw wykonać skan głębokości, kolorując czerwoną krawędzią, a następnie cofnąć się do napotkanego węzła pierwszego stopnia 3 i kontynuować skanowanie głębokości, najpierw kolorując zieloną krawędzią, i tak dalej. .. może ma bardziej formalną definicję, ale teraz nie przychodzi mi do głowy. Daj mi znać, jeśli potrzebujesz dodatkowych informacji.

— Vor

Widzę, że właściwość, że krawędzie są przesuwane w „poprawnym” kierunku, jest wymuszana przez ostatnią transformację. Dziękuję za wyjaśnienie.

— Wpis

Zainspirowany odpowiedzią Vora, chcę dać prostszą.

Rozpocznij od problemu cyklu Hamiltona dla problemu grafów siatkowych, który został udowodniony przez Itai.

Łatwo można zauważyć, że zestaw krawędzi wykresu siatki można podzielić na 2 rozłączne podzestawy: poziomy i pionowy.

Tak więc teraz musimy połączyć wszystkie poziome w jeden prosty cykl, a wszystkie w pionie w inny prosty cykl.

Jest to bardzo łatwe zadanie: w przypadku pionowych przeciągnij od lewej do prawej, po prostu połącz wszelkie pionowe szczeliny, a następnie połącz kolejne pionowe linie o współrzędnej x, a następnie połącz najniższy skrajny lewy wierzchołek z najwyższym skrajnym prawym wierzchołkiem. Zrób podobnie dla poziomych krawędzi.

Zauważ, że otrzymany wykres jest nadal prosty, bezkierunkowy i spełnia wymagania. Jest to proste, ponieważ na ostatnich etapach fazy pionowej i fazy poziomej mamy do czynienia z dwiema różnymi parami wierzchołków.

$k$ $k$ $2k|V|$

— Thinh D. Nguyen
źródło