Chcę, aby prosty gadżet udowodnił, że cyklarny plan Hamiltonian NP-Complete (od cyklu Hamiltonian)

Wiadomo, że cykl hamiltonowski (w skrócie szynka) jest zakończony NP, a cykl szynki Planar jest zakończony NP. Dowód na cykl szynkowy nie pochodzi z cyklu szynkowego.

Czy jest fajny gadżet, który, biorąc pod uwagę wykres G, zastąpi wszystkie skrzyżowania jakimś płaskim gadżetem, dzięki czemu masz płaski wykres G 'taki, że

G ma cykl szynki iff G 'ma cykl szynki.

(Będę zadowolony z wariantów takich jak Ścieżka Szynki lub ukierunkowany Cykl Szynki lub Ścieżka Szynki Kierowanej.)

cc.complexity-theory np-hardness planar-graphs hamiltonian-paths Bill GASARCH
źródło

Nieco trywialne spostrzeżenie. Załóżmy, że osadziłeś i krawędzie i krzyżują się, przy czym pojawiają się zgodnie z ruchem wskazówek zegara wokół punktu przecięcia. Zastąp go gadżetem który ma cztery punkty wejścia odpowiadające . Jeśli cykl hamiltonowski w wykorzystuje obie krawędzie i to w odpowiedni cykl musiałby się przeciąć. Zakłada to oczywiście najbardziej naiwną interpretację tego, czym jest `` gadżet '', a także, że cykl hamiltonowski w

G

$G$

(x, y)

$(x,y)$

(u, v)

$(u,v)$

x, v, y, u

$x,v,y,u$

P_{x v y u}

$P_{xvyu}$

x^{'}, v^{'}, y^{'}, u^{'}

$x',v',y',u'$

x, v, y, u

$x,v,y,u$

G

$G$

(x, y)

$(x,y)$

(u, v)

$(u,v)$

G^{'}

$G'$

G^{'}

$G'$ musi spełniać te same krawędzie do odpowiedniego cyklu .

G

$G$

Marek Chrobak

Co to jest cykl szynki? Nie zakładaj, że wszyscy rozumieją twoje skróty.

Tsuyoshi Ito

@MarekChrobak: Zgadzam się z twoją uwagą. Dajesz dwa sposoby na uniknięcie kłótni. Myślę, że najbardziej naturalna jest drugi: Jest Hamiltona Cykl w

wtedy i tylko wtedy istnieje Hamiltona Cykl

x \to y \to \dots \to u \to v \to \dots \to x

$x\to y\to\dotsb\to u\to v\to\dotsb\to x$

G

$G$

x \to x^{'} \to \dots \to u^{'} \to u \to \dots \to y \to y^{'} \to \dots \to v^{'} \to v \to \dots \to x

$x\to x'\to\dotsb \to u'\to u\to\dotsb\to y\to y'\to\dotsb\to v'\to v\to\dotsb\to x$

Bruno

@Tsuyoshi: To oznacza cykl hamiltonowski. Myślę, że rozsądnie jest założyć, że każdy może to rozgryźć.

domotorp

@ Bill: Zastanawiam się, dlaczego uważasz, że taki gadżet powinien istnieć. Liczba skrzyżowań przy osadzaniu dowolnego wykresu w płaszczyźnie może być bardzo duża (

dla pełnego wykresu - patrz lemat przecinający). Jeśli więc zaczniesz od wykresu z

krawędziami i wieloma krawędziami (powiedzmy prawie kwadratowe), wówczas wykres osadzony z dodanymi skrzyżowaniami jako wierzchołki ma zupełnie inną strukturę ...

Θ (n^{4})

$\Theta(n^4)$

n

$n$

Sariel Har-Peled

Odpowiedzi:

Nie. Przynajmniej żaden „miły” gadżet dla jednego crossovera.

Niech i będą krzyżem, który chcemy zastąpić. $(a, b)$ $(x,y)$ wprowadź opis zdjęcia tutaj

Istnieje wiele przypadków dla naszego wykresu, , ale musimy spełnić co najmniej następujące cztery. Przypadek 1: istnieje co najmniej jeden cykl hamiltonowski, ale żaden nie używa żadnej z krawędzi. Przypadek 2: istnieje co najmniej jeden cykl, a wszystkie cykle wykorzystują dokładnie jedną z dwóch krawędzi. Przypadek 3: istnieje co najmniej jeden cykl, a wszystkie cykle wykorzystują obie krawędzie. Przypadek 4: nie ma cyklu hamiltonowskiego. $G$

Jeśli nasz urządzenie ma dwa (lub więcej) wierzchołków każdego sąsiedztwie tymi samymi sąsiadów (tak i zachowują „S sąsiadów), wtedy nie muszą jednak być płaskie. Aby spełnić pierwszy z powyższych przypadków, nie możemy mieć żadnych nowych wierzchołków w gadżecie. $a, b, x, y$ $a_0$ $a_1$ $a$ $G'$

Aby spełnić powyższy przypadek 3, w gadżecie musimy mieć co najmniej dwie krawędzie. Ani para płaska i obejmująca, ani spełniają przypadku 2, więc potrzebujemy trzeciej krawędzi. Bez utraty ogólności niech te trzy będą . $(a, x), (y, b)$ $(a, y), (x, b)$ $(a, y), (y, b), (x,b)$

Zastąpienie to łamie jednak czwarty przypadek, ponieważ może zawierać cykl hamiltonowski, gdy nie. Weźmy, na przykład, , gdzie oraz $G'$ $G$ $G = (V, E)$ $V = \{a, b, x, y, p, q, r, s, t\},$ . nie jest płaskie i nie ma cyklu hamiltonowskiego. $E = \{(a, b), (x, y), (a, r), (a, p), (a, q), (b, s), (b, x), (p, s), (p, t), (p, y), (q, x), (r, y), (t, x)\}$ $G$ wprowadź opis zdjęcia tutaj

$G' = (V, E')$ $E' = \{(a, y), (y, b), (x, b)\} \cup$ $\{(x, y), (a, r), (a, p), (a, q), (b, s), (p, s), (p, t), (p, y), (q, x), (r, y), (t, x)\}$ $G'$ $a, q, x, t, p, s, b, y, r, a$

$(b, y)$ $(a, x)$ $G'$

$(a, b), (a, y), (x, b)$

Ponieważ dodanie trzech krawędzi łamie przypadek 4, dodanie więcej nie pomoże.

$a, b, x$ $y$

(Uwaga: daj mi znać, jeśli popełniłem błędy powyżej!)

( ~~Uwaga 2: Miałem kilka fajnych postaci, ale nie mogę ich~~ opublikować. Wysłano.)

Kyle
źródło

Myślę, że powinieneś teraz móc publikować dane liczbowe.

Jukka Suomela,