Проблем најдужег пута

У теорији графова и теоретској компјутерској науци, проблем најдужег пута је проблем проналажења простог пута највеће дужине у датом графу. Пут је прост ако се у њему не понавља ниједан чвор; дужина пута може се мерити или бројем његових грана, или сумом тежина грана тежинског графа. Насупрот Проблему најкраћег пута, који може бити решен у полиномијалном времену код графова без цицклуса негативних тежина, проблем најдужег пута је НП-тежак проблем, што значи да се не може решити у полиномијалном времену за произвољне графове сем ако је П = НП. Резултати јаче тежине показују да је тешко алгоритмички апроксимирати. Међутим, постоји решење у линеарном времену за усмерене ацикличне графове, што има значајну улогу у проналаску критичног пута у проблемима заказивања.

НП-тежина

Нп-тежина нетежинског проблема најдужег пута се може показати коришћењем редукције проблема Хамилтоновог пута: граф Г има Хамилтонов пут ако и само ако његов најдужи пут има дужину н − 1, где је н број чворова у Г. Из разлога што је Хамилтонов пут НП-комплетан проблем, ова редукција показује да је проблем најдужег пута такође НП-комплетан проблем. У овом проблему, улаз је граф Г и број к; жељени излаз је да уколико Г садржи пут од к или више грана, и не у супротном.

Ако би се проблем најдужег пута могао решити у полиномијалном времену, могао би се се користити да реши овај проблем одлуке, тако што би се пронашао најдужи пут и онда поредила његова дужина са бројем к. Стога, проблем најдужег пута је НП-тежак. Није НП-комплетан, зато што није проблем одлуке.

У усмереним комплетним графовима са не-негативним тежинама грана, тежински проблем најдужег пута је исти као и проблем трговачког путника, зато што најдужи пут увек уклучује све чворове.

Ациклични графови и критични путеви

Најдужи пут између два задата чвора с и т у тежинском графу Г је иста ствар као и најкраћи пут у графу −Г изведеном из Г мењањем сваке тежине у своју негацију. Стога, ако се најкраћи путеви могу пронаћи у −Г, тада најдужи путеви се такође могу пронаћи у Г.

За већину графова, ова трансформација није корисна зато што ствара циклусе негативне дужине у −Г. Али ако Г је усмерени ациклични граф, тада не могу бити створени никакви негативни циклуси, и најдужи пут у Г се може пронаћи у линеарном времену тако што применимо алгоритам линеарног времена за најкраће путеве у −Г, што је такође усмерени ациклични граф. На пример, за сваки чвор в у датом графу, дужина најдужег пута, који се завршава са в, може се добити у следећим корацима:

1. Пронаћи тополошко уређење датог графа
2. За сваки чвор в графа, у тополошком уређењу, израчунати дужину најдужег пута који се завршава са в гледајући наредне комшије и додајући један на максималну дужину забележену за те комшије. Ако в нема наредне комшије, поставити дужину најдужег пута, који се завршсава са в, на нулу. У оба случаја, забележити овај број тако да наредни кораци алгоритма могу да му приступе.

Када је ово учињено, најдужи пут у целом графу може се добити започињањем од чвора в са највећом забележеном вредношћу, а онда понављање корака у назад на његовог наредног комшију са највећом забележеном вредношћу, и обртање низа чворова који су пронађени овим путем.

Метод критичног пута за заказивање скупа активности укључује конструкцију усмереног ацикличног графа тако да чворови представљају прекретнице пројекта а гране представљају активности које морају бити учињене након једне прекретнице и пре друге; свака грана има тежину која се мери проценом количине времена која је потребна да се испуни нека активност. У оваквом графу, најдужи пут од прве прекретнице до последње је критични пут, који описује укупно време потребно за извршење пројекта.

Најдужи путеви усмереног ацикличног графа се могу такође употребити у слојевитом графичком цртању: сваки чвор в усмереног ацикличног графа Г представља слој чији број је дужина најдужег пута који се завршава са в.

Апроксимација

Бјорклунд, Хусфелдт и Кханна (2004) написали су да је проблем најдужег пута у нетежинским неусмереним графовима "познат по тежини разумевање његове апроксимације тежине". Алгоритам апроксимације у најбољем полиномијалном времену познат за овај случај бележи врло слаб однос апроксимације, $n/\exp(\Omega ({\sqrt {\log n}}))$. За све $\epsilon >0$, није могуће апроксимирати најдужи пут до фактора $2^{(\log n)^{1-\epsilon }}$ сем ако НП није садржан у оквиру квази-полиномијалног детерминистичког времена; међутим, постоји велики раскорак између немогућности апроксимације резултата и познате апроксимације алгоритма за овај проблем.

У случају нетежинског али усмереног графа, познати су снажни резултати немогућности апроксимације. За сваки $\epsilon >0$ проблем не може бити апроксимиран до фактора $n^{1-\epsilon }$ сем ако је П=НП, и са снажним претпоставкама теоретске комплексности не може бити апроксимирано до фактора $n/\log ^{2+\epsilon }n$.

Параметризована комплексност

Проблем најдужег пута је прилагодљив фиксном параметру када се параметризује дужином пута. На пример, може бити решен у времену линеарном величини улазног графа (али експоненцијалном дужини пута), алгоритмом који прати следеће кораке:

1. Извршити претрагу графа у дубину. Нека $d$ буде дубина добијеног стабла претраге у дубину.
2. Користити низ корен-лист путева претраге у дубину, у редоследу у ком су пређени претрагом, да се направи декомпозиција пута графа, са ширином пута $d$.
3. Применити динамичко програмирање на ову декомпозицију пута да се пронађе најдужи пут у времену $O(d!2^{d}n)$, где $n$ је број чворова графа.

Како излазни пут има дужину величине бар $d$, време трајања је такође ограничено са $O(\ell !2^{\ell }n)$, где $\ell$ је дужина најдужег пута. Користећи кодирање бојама, зависност дужине пута може се смањити на јединствену експоненцијалну. Сличне технике динамичког програмирања показују да проблем најдужег пута је такође прилагодљив фиксном параметру када се параметризује ширином дрвета графа.

За графове ограничене ширином клике, најдужи пут може бити решен у полиномијалном времену алгоритмом динамичког програмирања. Међутим, полиномијални експонент зависи од ширине клике графа, па овај алгоритам није прилагодљив фиксном параметру. Проблем најдужег пута, параметризован ширином клике, је тежак за класу параметризоване комплексности $W[1]$, што показује да алгоритам прилагодљив фиксном параметру вероватно не постоји.

Специјални случајеви графова

Проблем најдужег пута може се решити у полиномијалном времену на допунама упоредивих графова. Може се такође решити у полиномијалном времену на било којој класи графова са ограниченом ширином стабла или ограниченом ширином клика, као што су наследни графови. Међутим, то је НП-тешко и када је ограничено на расцепљене графове, кружне графове, или пљоснате графове.

Види још

• Галлаи–Хассе–Роy–Витавер теорема, однос између најдужег пута и бојења графа
• Најдужи непресечени пут коња у шаху
• Змија у кутији, најдужи индуковани пут у графу хиперкоцке

Спољашње везе

• "Финд тхе Лонгест Патх Архивирано на сајту Wayback Machine (14. јун 2010)", песма извођача Дан Баррет