Klasy wykresów, w których problemy cyklu Hamiltoniana i ścieżki Hamiltoniana mają różną złożoność

Podczas przeszukiwania Systemu informacji o klasach grafów i ich inkluzjach znalazłem kilka klas grafów, dla których problem cyklu Hamiltoniana jest NP-kompletny, natomiast złożoność problemów ścieżki Hamiltonian NIE jest znana. Niektóre z tych klas to dwuczęściowe wykresy o maksymalnym stopniu 3, wykresy o maksymalnym stopniu 3 i 2 połączone sześcienne wykresy płaskie. Zjawisko to dotyczy także wykresów kołowych i trójkątnych.

Czy istnieje aktualizacja złożoności problemu ścieżki Hamiltona w tych klasach? Czy istnieje wyjaśnienie tego zjawiska?

EDYCJA : W bazie danych klas grafów znalazłem dziwny przypadek grafów o stałej siatce, w których problem cyklu Hamiltona jest w podczas gdy problem ścieżki Hamiltona jest nieznanej złożoności. $P$

cc.complexity-theory graph-theory Mohammad Al-Turkistany
źródło

Zastanawiam się, czy istnieje interesująca klasa grafów, dla której HP jest w ale HC jest w stanie .

P

$P$

N P

$NP$

Mohammad Al-Turkistany,

Na ogół jest jakaś klasa wykres, dla których jednym z problemów (HC i HP) jest

-Complete, a druga jest w

lub

? Szukam opublikowanych wyników dla problemów z HC i HP.

N P

$NP$

P

$P$

N P I

$NPI$

Mohammad Al-Turkistany

Jak na to, co jest warte (niewiele), Hamiltonian Path i Hamiltonian Cycle mają różną złożoność na drzewach: cykl jest trywialny, ale ścieżka wymaga skanowania liniowego, aby sprawdzić, czy wierzchołek stopnia jest większy niż dwa.

David Richerby,

Jest mało prawdopodobne, że HP jest w

i HC jest

pełnoporcjowych dla każdej klasy grafów ponieważ jest redukcja Gotuj z KL do firmy HP, która sprawia, że co najwyżej

rozmowy do wyroczni HP. Prawdziwe pytanie brzmi, czy istnieje redukcja Karp (

P

$P$

N P

$NP$

O (| E |)

$O(|E|)$

H C <_{P}^{m} H P

$HC<_P^m HP$

Mohammad Al-Turkistany,

Odpowiedzi:

Hamiltonian Problem ścieżka na wykresach siatki z maksymalnym stopniu 3 jest NP-zupełny. Dowód znajduje się w CH Papadimitriou i UV Vazirani, O dwóch problemach geometrycznych związanych z problemem podróżnego sprzedawcy, Journal of Algorytmy, tom 5, wydanie 2, czerwiec 1984, strony 231–246 (Twierdzenie 2)

Marzio De Biasi
źródło

Dzięki Marzio, czy używają tej samej definicji, która jest używana w bazie danych dla grafów gridowych? (ponieważ są to różne definicje w literaturze)

Mohammad Al-Turkistany,

Wykres siatki jest skończonym, indukowanym przez węzeł podrożnikiem

, nieskończonym wykresem, którego zestaw wierzchołków składa się ze wszystkich punktów płaszczyzny o współrzędnych całkowitych i w których dwa wierzchołki są połączone, tylko wtedy, gdy odległość euklidesowa między nimi wynosi 1; tak wykres siatka może mieć „dziury” i twierdzenie jest spełniony (wyłącznie) wykresów sieci, w której wierzchołki mają maksymalny stopień 3.

G^{\infty}

$G^\infty$

Marzio De Biasi

Dzięki Marzio, więc dla tej klasy HC i HP mają tę samą złożoność.

Mohammad Al-Turkistany,

@ MohammadAl-Turkistany: kolejna uwaga: wykresy siatki (i wykresy z maksymalnym stopniem 3) są również dwustronne, więc HP powinno być NP-kompletne dla grafów dwustronnych z maksymalnym stopniem 3.

Marzio De Biasi,

Zaktualizowano system informacyjny o klasach grafów i ich włączeniach. Teraz problem cyklu Hamiltona i problem ścieżki Hamiltona są określane jako NP-zupełne na 2-połączonych sześciennych grafach płaskich.

Jednak złożoności obliczeniowe problemów HC i HP są wymienione jako nieznane dla jednego problemu i NP-zupełne dla drugiego na wykresach kołowych , trójkątnych i stałych .

Mohammad Al-Turkistany
źródło

Mówisz „… złożoność problemów HC i HP jest wciąż inna…”; może lepiej powiedzieć, że „dla tych klas grafów HC to NPC, ale HP wciąż nie zna złożoności”

Marzio De Biasi

@MarzioDeBiasi Dziękujemy za cenny komentarz. Zredagowałem, aby odzwierciedlić twoją sugestię.

Mohammad Al-Turkistany

Czy coś mi umknęło? HC to wielomian czasowy rozwiązalny w grafach o stałej siatce. ieeexplore.ieee.org/document/646138

Saeed