Problem najdužeg puta

U teoriji grafova i teoretskoj kompjuterskoj nauci, problem najdužeg puta je problem pronalaženja prostog puta najveće dužine u datom grafu. Put je prost ako se u njemu ne ponavlja nijedan čvor; dužina puta može se meriti ili brojem njegovih grana, ili sumom težina grana težinskog grafa. Nasuprot Problemu najkraćeg puta, koji može biti rešen u polinomijalnom vremenu kod grafova bez cicklusa negativnih težina, problem najdužeg puta je NP-težak problem, što znači da se ne može rešiti u polinomijalnom vremenu za proizvoljne grafove sem ako je P = NP. Rezultati jače težine pokazuju da je teško algoritmički aproksimirati. Međutim, postoji rešenje u linearnom vremenu za usmerene aciklične grafove, što ima značajnu ulogu u pronalasku kritičnog puta u problemima zakazivanja.

NP-težina

Np-težina netežinskog problema najdužeg puta se može pokazati korišćenjem redukcije problema Hamiltonovog puta: graf G ima Hamiltonov put ako i samo ako njegov najduži put ima dužinu n − 1, gde je n broj čvorova u G. Iz razloga što je Hamiltonov put NP-kompletan problem, ova redukcija pokazuje da je problem najdužeg puta takođe NP-kompletan problem. U ovom problemu, ulaz je graf G i broj k; željeni izlaz je da ukoliko G sadrži put od k ili više grana, i ne u suprotnom.

Ako bi se problem najdužeg puta mogao rešiti u polinomijalnom vremenu, mogao bi se se koristiti da reši ovaj problem odluke, tako što bi se pronašao najduži put i onda poredila njegova dužina sa brojem k. Stoga, problem najdužeg puta je NP-težak. Nije NP-kompletan, zato što nije problem odluke.

U usmerenim kompletnim grafovima sa ne-negativnim težinama grana, težinski problem najdužeg puta je isti kao i problem trgovačkog putnika, zato što najduži put uvek uklučuje sve čvorove.

Aciklični grafovi i kritični putevi

Najduži put između dva zadata čvora s i t u težinskom grafu G je ista stvar kao i najkraći put u grafu −G izvedenom iz G menjanjem svake težine u svoju negaciju. Stoga, ako se najkraći putevi mogu pronaći u −G, tada najduži putevi se takođe mogu pronaći u G.

Za većinu grafova, ova transformacija nije korisna zato što stvara cikluse negativne dužine u −G. Ali ako G je usmereni aciklični graf, tada ne mogu biti stvoreni nikakvi negativni ciklusi, i najduži put u G se može pronaći u linearnom vremenu tako što primenimo algoritam linearnog vremena za najkraće puteve u −G, što je takođe usmereni aciklični graf. Na primer, za svaki čvor v u datom grafu, dužina najdužeg puta, koji se završava sa v, može se dobiti u sledećim koracima:

1. Pronaći topološko uređenje datog grafa
2. Za svaki čvor v grafa, u topološkom uređenju, izračunati dužinu najdužeg puta koji se završava sa v gledajući naredne komšije i dodajući jedan na maksimalnu dužinu zabeleženu za te komšije. Ako v nema naredne komšije, postaviti dužinu najdužeg puta, koji se završsava sa v, na nulu. U oba slučaja, zabeležiti ovaj broj tako da naredni koraci algoritma mogu da mu pristupe.

Kada je ovo učinjeno, najduži put u celom grafu može se dobiti započinjanjem od čvora v sa najvećom zabeleženom vrednošću, a onda ponavljanje koraka u nazad na njegovog narednog komšiju sa najvećom zabeleženom vrednošću, i obrtanje niza čvorova koji su pronađeni ovim putem.

Metod kritičnog puta za zakazivanje skupa aktivnosti uključuje konstrukciju usmerenog acikličnog grafa tako da čvorovi predstavljaju prekretnice projekta a grane predstavljaju aktivnosti koje moraju biti učinjene nakon jedne prekretnice i pre druge; svaka grana ima težinu koja se meri procenom količine vremena koja je potrebna da se ispuni neka aktivnost. U ovakvom grafu, najduži put od prve prekretnice do poslednje je kritični put, koji opisuje ukupno vreme potrebno za izvršenje projekta.

Najduži putevi usmerenog acikličnog grafa se mogu takođe upotrebiti u slojevitom grafičkom crtanju: svaki čvor v usmerenog acikličnog grafa G predstavlja sloj čiji broj je dužina najdužeg puta koji se završava sa v.

Aproksimacija

Bjorklund, Husfeldt i Khanna (2004) napisali su da je problem najdužeg puta u netežinskim neusmerenim grafovima "poznat po težini razumevanje njegove aproksimacije težine". Algoritam aproksimacije u najboljem polinomijalnom vremenu poznat za ovaj slučaj beleži vrlo slab odnos aproksimacije, $n/\exp(\Omega ({\sqrt {\log n}}))$. Za sve $\epsilon >0$, nije moguće aproksimirati najduži put do faktora $2^{(\log n)^{1-\epsilon }}$ sem ako NP nije sadržan u okviru kvazi-polinomijalnog determinističkog vremena; međutim, postoji veliki raskorak između nemogućnosti aproksimacije rezultata i poznate aproksimacije algoritma za ovaj problem.

U slučaju netežinskog ali usmerenog grafa, poznati su snažni rezultati nemogućnosti aproksimacije. Za svaki $\epsilon >0$ problem ne može biti aproksimiran do faktora $n^{1-\epsilon }$ sem ako je P=NP, i sa snažnim pretpostavkama teoretske kompleksnosti ne može biti aproksimirano do faktora $n/\log ^{2+\epsilon }n$.

Parametrizovana kompleksnost

Problem najdužeg puta je prilagodljiv fiksnom parametru kada se parametrizuje dužinom puta. Na primer, može biti rešen u vremenu linearnom veličini ulaznog grafa (ali eksponencijalnom dužini puta), algoritmom koji prati sledeće korake:

1. Izvršiti pretragu grafa u dubinu. Neka $d$ bude dubina dobijenog stabla pretrage u dubinu.
2. Koristiti niz koren-list puteva pretrage u dubinu, u redosledu u kom su pređeni pretragom, da se napravi dekompozicija puta grafa, sa širinom puta $d$.
3. Primeniti dinamičko programiranje na ovu dekompoziciju puta da se pronađe najduži put u vremenu $O(d!2^{d}n)$, gde $n$ je broj čvorova grafa.

Kako izlazni put ima dužinu veličine bar $d$, vreme trajanja je takođe ograničeno sa $O(\ell !2^{\ell }n)$, gde $\ell$ je dužina najdužeg puta. Koristeći kodiranje bojama, zavisnost dužine puta može se smanjiti na jedinstvenu eksponencijalnu. Slične tehnike dinamičkog programiranja pokazuju da problem najdužeg puta je takođe prilagodljiv fiksnom parametru kada se parametrizuje širinom drveta grafa.

Za grafove ograničene širinom klike, najduži put može biti rešen u polinomijalnom vremenu algoritmom dinamičkog programiranja. Međutim, polinomijalni eksponent zavisi od širine klike grafa, pa ovaj algoritam nije prilagodljiv fiksnom parametru. Problem najdužeg puta, parametrizovan širinom klike, je težak za klasu parametrizovane kompleksnosti $W[1]$, što pokazuje da algoritam prilagodljiv fiksnom parametru verovatno ne postoji.

Specijalni slučajevi grafova

Problem najdužeg puta može se rešiti u polinomijalnom vremenu na dopunama uporedivih grafova. Može se takođe rešiti u polinomijalnom vremenu na bilo kojoj klasi grafova sa ograničenom širinom stabla ili ograničenom širinom klika, kao što su nasledni grafovi. Međutim, to je NP-teško i kada je ograničeno na rascepljene grafove, kružne grafove, ili pljosnate grafove.

Vidi još

• Gallai–Hasse–Roy–Vitaver teorema, odnos između najdužeg puta i bojenja grafa
• Najduži nepresečeni put konja u šahu
• Zmija u kutiji, najduži indukovani put u grafu hiperkocke

Spoljašnje veze

• "Find the Longest Path Архивирано на сајту Wayback Machine (14. јун 2010)", pesma izvođača Dan Barret