Problema drumului hamiltonian

În domeniul matematic al teoriei grafurilor, problema drumului hamiltonian și problema ciclului hamiltonian sunt problemele care cer să se determine dacă există un drum hamiltonian (un drum într-un graf orientat sau neorientat, care vizitează fiecare nod exact o dată) sau un ciclu hamiltonian într-un graf dat (indiferent dacă este orientat sau neorientat). Ambele probleme sunt NP-complete.

Problema ciclului hamiltonian este un caz special al problemei comis-voiajorului, obținut prin stabilirea distanței dintre două orașe la unu dacă sunt adiacente și doi altfel, și verificând că distanța totală parcursă este egală cu n (dacă da, atunci drumul este un ciclu Hamiltonian, iar dacă nu există un ciclu hamiltonian, atunci cel mai scurt drum va fi mai lung decât atât).

Reducerea între problema drumului și problema ciclului

Există o relație simplă între problemele drumului hamiltonian și ciclului hamiltonian:

• Într-o direcție, problema drumului hamiltonian pentru graful G este echivalentă cu problema ciclului hamiltonian într-un graf H obținut din G prin adăugarea unui nou nod x și prin conectarea lui x la toate nodurile lui G. Astfel, găsirea unui drum hamiltonian nu poate fi semnificativ mai lentă (în cel mai rău caz, ca funcție de numărul de noduri) decât găsirea unui ciclu hamiltonian.
• În cealaltă direcție, problema ciclului hamiltonian pentru un graf G este echivalentă cu problema drumului hamiltonian din graful H obținut prin copierea unui nod v al lui G, v', adică permițându-i lui v' să aibă aceeași vecinătate ca și v, și prin adăugarea a două noduri false de grad unu, și conectându-le cu v și, respectiv, v'.

Algoritmi

Există n! secvențe diferite de noduri care ar putea fi drumuri hamiltoniene într-un graf dat cu n noduri (și, într-un graf complet, chiar sunt), astfel încât un algoritm de căutare cu forță brută^⁠(d) care testează toate șirurile posibile ar fi foarte lent. Unul din primii algoritmi exacți pentru găsirea unui ciclu hamiltonian pe un graf orientat a fost algoritmul enumerator al lui Martello. O procedură de căutare a lui Frank Rubin împarte muchiile grafului în trei clase: cele care trebuie să fie în drum, cele care nu pot fi în drum și cele nedeterminate. Pe măsură ce căutarea avansează, un set de reguli de decizie clasifică muchiile nedeterminate și determină oprirea sau continuarea căutării. Algoritmul împarte graful în componente care pot fi rezolvate separat. De asemenea, un algoritm de programare dinamică^⁠(d) al lui Bellman, Held și Karp poate fi folosit pentru a rezolva problema în timp O(n²2ⁿ). În această metodă, se determină, pentru fiecare mulțime S de noduri și fiecare nod v din S, dacă există un drum care acoperă exact nodurile din S și se termină în v. Pentru fiecare alegere a S și v, există un drum pentru (S, v) dacă și numai dacă v are un vecin w astfel încât există un drum pentru (S − v, w), ceea ce se poate căuta din informațiile deja calculate în programul dinamic.

Andreas Björklund a oferit o abordare alternativă folosind principiul includere-excludere^⁠(d) pentru a reduce problema numărării ciclurilor hamiltoniene la o problemă de numărare mai simplă, a numărării acoperirilor ciclurilor, problemă care poate fi rezolvată prin calcularea anumitor determinanți de matrice. Folosind această metodă, el a arătat cum se rezolvă problema ciclului hamiltonian în grafuri arbitrare cu n noduri printr-un algoritm Monte Carlo^⁠(d) în timp O(1,657ⁿ); pentru grafuri bipartite acest algoritm poate fi îmbunătățit în continuare la timpul o(1,415ⁿ).

Pentru grafurile de grad maxim trei, o căutare atentă cu backtracking poate găsi un ciclu hamiltonian (dacă există) în timp O(1,251ⁿ).

Drumurile și ciclurile hamiltoniene pot fi găsite folosind un rezolvitor SAT^⁠(d) .

Din cauza dificultății de rezolvare a problemelor drumului și ciclului hamiltonian pe calculatoarele convenționale, ele au fost studiate și pe modele neconvenționale de calcul. De exemplu, Leonard Adleman a arătat că problema drumului Hamiltonian poate fi rezolvată folosind un calculator cu ADN. Exploatând paralelismul inerent reacțiilor chimice, problema poate fi rezolvată folosind un număr de etape de reacție chimică liniară în numărul de noduri ale grafului; totuși, necesită un număr factorial de molecule ADN care să participe la reacție.

S-a propus și o soluție optică la problema hamiltoniană.. Ideea este de a crea o structură asemănătoare grafurilor, realizată din cabluri optice și separatoare de fascicule care sunt traversate de lumină pentru a construi o soluție pentru problemă. Punctul slab al acestei abordări este cantitatea necesară de energie care este exponențială în numărul de noduri.

Complexitate

Problema găsirii unui ciclu sau drum hamiltonian este în FNP^⁠(d); problema deciziei^⁠(d) analoge este de a testa dacă există un ciclu sau drum hamiltonian. Problemele ciclului hamiltonian pe grafuri orientate și neorientate au fost două dintre cele 21 de probleme NP-complete ale lui Karp. Acestea rămân NP-complete chiar și pentru tipuri speciale de grafuri, cum ar fi:

• grafuri bipartite,
• grafuri planare neorientate cu grad maxim trei,
• grafuri planare orientate cu grad interior și exterior maxim doi,
• grafuri bipartite neorientate, planare, 3-regulate, fără punți
• grafuri bipartite 3-conectate 3-regulate,
• subgrafuri ale grafului grilă pătrată^⁠(d),
• subgrafurile cubice ale grafului grilă pătrată.

Cu toate acestea, pentru unele clase speciale de grafuri, problema poate fi rezolvată în timp polinomial:

• Grafurile planare 4-conectate sunt întotdeauna hamiltoniene datorită unui rezultat datorat lui Tutte, iar sarcina computațională de a găsi un ciclu Hamiltonian în aceste grafuri poate fi efectuată în timp liniar prin calcularea unui așa-numite drum Tutte.
• Tutte a demonstrat acest rezultat arătând că orice graf planar 2-conectat conține un drum Tutte. Drumurile Tutte pot fi calculate la rândul lor în timp pătratic chiar și pentru grafuri planare 2-conectate, care pot fi folosite pentru a găsi cicluri hamiltoniene și cicluri lungi în generalizări ale grafurilor planare.

Dacă toate aceste condiții se îndeplinesc împreună, rămâne deschis dacă grafurile planare bipartite 3-conectate 3-regulate conțin întotdeauna un ciclu hamiltonian, caz în care problema limitată la acele grafuri nu ar putea fi NP-completă; vezi conjectura lui Barnette^⁠(d).

În grafuri în care toate nodurile au un grad impar, un argument referitor la lema strângerilor de mâini^⁠(d) arată că numărul de cicluri hamiltoniene prin orice muchie fixă este întotdeauna par, deci dacă se dă un ciclu hamiltonian, atunci trebuie să existe și al doilea. Totuși, găsirea acestui al doilea ciclu nu pare să fie o sarcină computațională ușoară. Papadimitriou a definit clasa de complexitate PPA^⁠(d) pentru a încapsula probleme ca aceasta.