Cykl hamiltonowski na wykresach bez małych cykli

Odpowiadając na to pytanie w cstheory , (nieformalnie) udowodniłem w locie następujące twierdzenie:

Twierdzenie : Dla dowolnego ustalonego sonda cyklu Hamiltoniana pozostaje NP-kompletna, nawet jeśli jest ograniczona do płaskich dwustronnych grafów niekierowanych o maksymalnym stopniu 3, które nie zawierają cykli o długości . $l \geq 3$ $\leq l$

Wydaje się bardzo mało prawdopodobne, aby gdzieś się jeszcze nie pojawiło.
Pozwala to jednak rozwiązać wiele problemów związanych z cyklem / ścieżką hamiltonowską na graphclasses.org, które są oznaczone jako „Nieznane ISGCI” (patrz na przykład ten ); Rzeczywiście bezpośrednim następstwem jest to, że problemy związane z cyklem Hamiltona i ścieżek jeszcze NP-zupełny, jeżeli ograniczone do wykresy, gdzie każdy z zawiera co najmniej jeden cykl. $(H_1,...,H_k)\text{-free}$ $H_i$

Czy możesz podać mi odniesienie do gazety / książki, w której się ukazało?

(wtedy skontaktuję się z ludźmi na graphclasses.org)

reference-request np-hardness Marzio De Biasi
źródło

Przynajmniej te dyskusje pomogły w uzyskaniu nowych wyników w graphclasses.org, dlatego prosimy o informowanie graphclasses o nieznanych im wynikach - link Kontakt zawiera formularz, adres e-mail jest opcjonalny.

joro

@joro: Już się z nimi skontaktowałem wczoraj (również dałem im swój e-mail). Poczekam kilka dni i sprawdzę, czy zaktualizują stan tych problemów.

Marzio De Biasi,

Słyszałem, że nie aktualizują bazy danych bardzo często i odpowiadają po podziękowaniu po aktualizacji bazy danych i są dość responsywni.

joro

@joro: Myślę, że zaktualizowali bazę danych (są bardzo chętni do współpracy i uprzejmi)

Marzio De Biasi

Odpowiedzi:

Wynik jest podany w artykule Dwie nowe klasy grafów hamiltonowskich autorstwa Arkina, Mitchella i Polinshchuka.

Kristoffer Arnsfelt Hansen
źródło

Ten niepublikowany rękopis Hougardy, Emden-Weinert i Kreuter z 1997 r. Stanowił prosty dowód na następujący wynik, który jest znacznie silniejszy niż wynik wskazany w odpowiedzi Kristoffera Arnsfelt Hansen:

$0\le r <1/2$ $n$ $\ge n^r$

Manuskrypt zawiera również podobne wyniki dla innych problemów, takich jak Dominujący zestaw, Max cięcia, VFS itp.

vb le
źródło

Ok dzięki! Zapomniałem wspomnieć, że mój dowód działa dla płaskich dwukierunkowych grafów bezkierunkowych o maksymalnym stopniu 3 ... więc Hourgardy i in. papier jest mocniejszy ... ale niewiele silniejszy :-) :-). Prawdopodobnie zaakceptuję odpowiedź Kristoffera, ponieważ opublikował ją jako pierwszą.

Marzio De Biasi,

@MarzioDeBiasi, myślę, że siła polega na wielkości obwodu. twój dowód dotyczy stałej liczby, akceptowana odpowiedź jest dla niektórych f (n), które są mniejsze niż sqrt i ta odpowiedź jest bardziej ogólna niż wszystkie. (Ograniczenie IMHO do wykresu nie jest tutaj bardzo ważne)

Saeed

Artykuł zawiera inne problemy trudne dla NP, będzie odpowiedzią na powiązane pytanie dotyczące grafów cyklicznych.

joro