În teoria graficelor și în informatică teoretică , cea mai lungă problemă a lanțului (sau cea mai lungă problemă de cale în cazul unui grafic direcționat) constă în determinarea celui mai lung lanț elementar dintr-un grafic. Un lanț este elementar dacă nu trece de două ori prin același vârf. Lungimea unui lanț poate fi măsurată prin numărul de muchii care o compun sau, în cazul graficelor ponderate , prin suma greutăților marginilor căii.
Spre deosebire de cea mai scurtă problemă de cale , care poate fi rezolvată în timp polinomial în grafice fără cicluri de greutate negative, cea mai lungă problemă a lanțului este NP-completă ; nu poate fi deci rezolvat în timp polinomial , cu excepția cazului în care P = NP . Rezultate suplimentare arată că, în plus, această problemă este, de asemenea, dificil de rezolvat într-un mod aproximativ . Pe de altă parte, are o complexitate liniară pentru graficele aciclice direcționate și are apoi aplicații importante, de exemplu în determinarea căii critice în problemele de planificare , deoarece acestea sunt modelate în metoda PERT , de exemplu.
Pentru a vedea că cea mai lungă problemă a lanțului este NP-hard, chiar și în grafice neponderate, folosim o reducere la problema lanțului hamiltonian : un grafic G are un lanț hamiltonian dacă și numai dacă cel mai lung lanț elementar din G are lungimea n -1 , unde n este numărul de noduri ale G . Deoarece știm că problema lanțului hamiltonian este NP-completă, această reducere arată că cea mai lungă problemă a lanțului, văzută ca o problemă de decizie , este și NP-completă. În această problemă de decizie, datele sunt formate dintr-un grafic G și un număr întreg k ; rezultatul este „da” dacă G are un șir de lungime k sau mai mult și „nu” în caz contrar.
Acum, dacă cea mai lungă problemă a șirului ar putea fi rezolvată în timp polinomial, ar putea fi utilizată pentru a rezolva problema deciziei, calculând mai întâi un șir mai lung și apoi comparând lungimea acestuia cu numărul întreg k , al doilea parametru al problemei. Acest lucru arată că cea mai lungă problemă a lanțului este NP-hard; nu este complet NP în măsura în care această noțiune se aplică doar unei probleme de decizie.
Într-un grafic complet ponderat, unde marginile poartă greutăți non-negative, cea mai lungă problemă a lanțului este aceeași cu problema vânzătorului călător , deoarece cel mai lung lanț trece întotdeauna prin toate vârfurile.
O cale cu greutate maximă între două vârfuri s și t a unui grafic ponderat G este aceeași cu o cale cu greutate minimă între s și t în graficul cu greutăți opuse, notat - G, obținut din G prin înlocuirea fiecărei greutăți cu opusul său valoare. Prin urmare, în cazul în care se pot găsi căi minime de greutate în - G , se pot găsi căile maxime de greutate în G . Cu toate acestea, această transformare nu este în general utilă deoarece creează circuite cu greutate negativă în - G , ceea ce face calculul traseelor minime mai complicat. Pe de altă parte, dacă G este un grafic direcționat aciclic , graficul - G este la fel de aciclic și o cale cu greutatea maximă în G poate fi găsită în timp liniar prin aplicarea unui algoritm liniar de calcul de cale mai scurt la - G , sau prin folosind un algoritm direct ca cel de mai jos.
Putem calcula o cale de lungime maximă, într-un grafic direcționat aciclic și neponderat, în doi pași: găsim mai întâi lungimea celor mai lungi căi care se termină într-un vârf dat v, pentru toate v, apoi găsim valoarea maximă dintre aceste lungimi .
În primul pas, operăm după cum urmează în două etape:
După calcularea lungimii celei mai lungi căi care ajunge la v pentru fiecare vârf v , găsim o cale cu lungimea maximă după cum urmează; începem prin alegerea unui vârf v cu cea mai mare valoare înregistrată, apoi în sus, căutăm în mod iterativ un vecin antecedent al lui v cu valoarea înregistrată mare. Seria vârfurilor vizitate este continuarea, în ordine inversă, a unei căi de lungime maximă.
Calea critică . Metoda căii critice pentru planificarea unui set de sarcini sau activități folosește construcția unui grafic direcționat aciclic: vârfurile reprezintă pași sau repere ale proiectului și arcurile sarcinilor care trebuie îndeplinite între un pas și următorul; fiecare arc este ponderat de o estimare a timpului necesar pentru a finaliza sarcina corespunzătoare. Într-un astfel de grafic, o cale mai lungă de la etapa inițială la etapa finală este o cale critică, a cărei lungime descrie timpul total necesar pentru finalizarea proiectului. Metoda PERT folosește această noțiune, cu evoluții considerabile în special pentru a include elemente care țin cont de situații neprevăzute.
Trasarea graficelor . O altă aplicație a celor mai lungi căi din graficele aciclice este desenarea graficelor după nivel (în) : atribuim fiecărui vârf v al unui grafic direcționat aciclic G un nivel al cărui număr este lungimea celei mai lungi căi care ajunge în v . Obținem astfel o atribuire a nivelurilor vârfurilor grafului cu un minim de straturi și care are proprietatea că un arc conectează vârfurile pe straturi cu valori crescânde.
Deoarece problema este dificilă, căutăm algoritmi de aproximare în timp polinomial, cu un raport de aproximare cât mai bun posibil și un timp care crește doar polinomial cu precizia de aproximare dorită.
Există un algoritm de aproximare a timpului polinomial, al cărui raport de aproximare pentru un grafic cu n vârfuri este și care nu este considerat foarte satisfăcător. Putem arăta că, în ipoteza P ≠ NP , nu este posibilă aproximarea în timp deterministic cvasi-polinomial a lungimii celui mai lung lanț cu un raport de pentru un dat; cu toate acestea, există un decalaj mare între acest rezultat al imposibilității de aproximare și metodele de aproximare cunoscute. În cazul graficelor direcționate și neponderate, cunoaștem rezultate mai precise pentru imposibilitatea aproximărilor. Căci întreaga problemă nu poate fi abordată cu un factor decât dacă P = NP și, sub anumite ipoteze mai puternice, nu poate fi abordată cu un factor . Codarea tehnică a culorilor (în) poate fi utilizată pentru a găsi o lungime a căii logaritmice în funcție de dimensiunea graficului dacă există o astfel de cale, dar numai raportul de aproximare .
Cea mai lungă problemă a lanțului este „ tratabilă cu parametri fixi ” atunci când este parametrizată de lungimea lanțului. De exemplu, poate fi rezolvat în timp liniar în dimensiunea graficului, dar exponențial în lungimea șirului, prin următoarea metodă:
Deoarece calea rezultată este cel puțin lungă , timpul de calcul poate fi, de asemenea, delimitat de , unde este lungimea celei mai lungi căi. Prin utilizarea tehnicii de codare a culorilor, complexitatea în funcție de lungimea traseului poate fi redusă la un exponențial simplu. O tehnică de programare dinamică similară arată că cea mai lungă problemă de cale este, de asemenea , parametru fix tratabil, atunci când este parametrizată de lățimea arborelui graficului.
Pentru graficele cu lățime de clic mărginită (en) , cea mai lungă problemă de șir poate fi rezolvată în timp polinomial printr-un algoritm de programare dinamică. Exponentul depinde de lățimea clicului, astfel încât algoritmul nu este tratabil cu parametri fixi . Cea mai lungă problemă a lanțului, parametrizată de lățimea clicului, este o problemă dificilă pentru clasa de complexitate parametrizată , care arată că existența unui algoritm cu parametri fix tractabili este puțin probabilă.
O familie de grafice în care problema poate fi rezolvată în timp polinomial este formată din graficele complementare ale comparabilității ; pentru aceste grafice, a fost dezvoltat un algoritm pentru un grafic cu n vârfuri, bazat pe tehnica LDFS ( lexicografic adâncime-prima căutare ).
Alte clase în care problema poate fi rezolvată în timp polinomial sunt cele ale graficelor cu lățimea arborelui delimitat sau lățimii clicului delimitat sau clasa graficelor complet separabile (ro) . Dar problema rămâne NP-dificilă pentru alte familii, cum ar fi graficele divizate , graficele de cerc sau graficele plane .