Zliczanie liczby cykli hamiltonowskich na sześciennych grafach hamiltonowskich?

15

Jest -hard znaleźć czynnik stały przybliżenie najdłuższego cyklu sześciennych Hamiltona wykresach. Sześcienne wykresy hamiltonowskie mają co najmniej dwa cykle hamiltonowskie. $NP$

Jakie są najbardziej znane wartości górnej i dolnej granicy liczby cykli hamiltonowskich na sześciennych grafach hamiltonowskich? Biorąc pod uwagę sześcienny wykres hamiltonowski, jaka jest złożoność znalezienia liczby cykli hamiltonowskich? Czy to # twardy? $P$

cc.complexity-theory counting-complexity

— Mohammad Al-Turkistany
źródło

20

Zliczanie obwodów hamiltonowskich na 3-regularnym wykresie hamiltonowskim jest # P-kompletne, jak następuje.

Szkic próbny . Członkostwo w #P jest banalne, więc pokażemy tylko twardość # P.

Sekcja 3 Liśkiewicza, Ogihary i Tody [LOT03] pokazuje, że zliczanie obwodów hamiltonowskich na wykresie 3-regularnym (i faktycznie planarnym w tym samym czasie) jest # P-kompletne. Co więcej, ich redukcja z map # 3SAT zadowalającą formułę 3CNF do grafów hamiltonowskich. Dlatego można zredukować # 3SAT do zliczania obwodów hamiltonowskich na 3-regularnym grafie hamiltonowskim, najpierw dodając jedno trywialne rozwiązanie do danej formuły 3CNF, a następnie redukując je do zliczania obwodów hamiltonowskich, stosując redukcję [LOT03]. QED .

[LOT03] Maciej Liśkiewicz, Mitsunori Ogihara i Seinosuke Toda. Złożoność liczenia samodzielnych spacerów w podgrafach dwuwymiarowych siatek i hipersześcianów. Teoretyczne Computer Science , 304 (1-3): 129-156, lipca 2003 http://dx.doi.org/10.1016/S0304-3975(03)00080-X

— Tsuyoshi Ito
źródło

Niezła odpowiedź. Czy znasz jakieś górną lub dolną granicę liczby cykli hamiltonowskich na sześciennych grafach hamiltonowskich?

— Mohammad Al-Turkistany

1

@turkistany można wygenerować 3-regularny wykres z wykładniczo wielu Hamiltona obwodów stosując powyższą zmniejszenie do wzoru 3CNF wykładniczo z wielu zadań spełniających (patrz Następstwem 6 z [LOT03] i definicji „

-reductions ”W sekcji 2.2), chociaż podejrzewam, że istnieje prostszy bezpośredni dowód. Nie znam żadnej dolnej granicy oprócz 2 (o której już wspomniałeś w pytaniu) ani żadnego dowodu, że 2 jest optymalny.

\leq_{r-shift}^{p}

$\le^p_{\text{r-shift}}$

— Tsuyoshi Ito

23

$2^{3n/8}$ $2^{n/3}$ $2^{n/3}$ $1.276^n$

$2^{n/2}$

— David Eppstein
źródło

Dzięki David za miłą odpowiedź. Chciałbym móc przyjąć więcej niż jedną odpowiedź.

— Mohammad Al-Turkistany

8

Niektóre wykresy mają dokładnie trzy obwody hamiltonowskie:

http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190060218/abstract

Jeśli zaczniemy od płaskiego wykresu czworościanu, który zawiera dokładnie trzy obwody hamiltonowskie, i utworzymy nowy płaski wykres 3 połączony przez obcinanie pojedynczego wierzchołka, otrzymamy nowy wykres, który ma dokładnie trzy obwody hamiltonowskie. Jeśli nadal obcina się jeden wierzchołek naraz, otrzymuje się rodzinę wykresów z dokładnie trzema obwodami hamiltonowskimi.

Dodatkowy komentarz:

Było także trochę pracy nad pytaniem, które wykresy inne niż cykle mają dokładnie jeden obwód hamiltonionowy:

http://www3.interscience.wiley.com/journal/113386600/abstract

Bardzo ładny artykuł ankietowy na temat obwodów hamlionowych na specjalnych rodzajach wykresów, który zawiera sekcję dotyczącą liczby obwodów hamiltonowskich i naprawia niektóre problemy z powyższym tekstem:

http://ajc.maths.uq.edu.au/pdf/20/ajc-v20-p111.pdf

— Joseph Malkevitch
źródło