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