Längsta vägen problem - Longest path problem

I grafteori och teoretisk datavetenskap är det längsta vägproblemet problemet att hitta en enkel väg med maximal längd i en given graf. En sökväg kallas enkel om den inte har några upprepade hörn; längden på en bana kan antingen mätas med dess antal kanter eller (i viktade grafer ) med summan av vikterna på dess kanter. Till skillnad från det kortaste banproblemet , som kan lösas i polynomtid i grafer utan negativviktscykler, är det längsta banproblemet NP-svårt och beslutsversionen av problemet, som frågar om det finns en väg av åtminstone en viss given längd, är NP-komplett . Detta innebär att beslutsproblemet inte kan lösas på polynom för godtyckliga diagram om inte  P = NP . Starkare hårdhetsresultat är också kända som visar att det är svårt att approximera . Den har dock en linjär tidslösning för riktade acykliska grafer , som har viktiga applikationer för att hitta den kritiska vägen vid schemaläggningsproblem.

NP-hårdhet

NP-hårdheten för det obevägade längsta banproblemet kan visas med en reduktion från Hamilton-banans problem : en graf G har en Hamilton-väg om och endast om dess längsta väg har längd n  - 1, där n är antalet hörn i G . Eftersom Hamiltonian-vägproblemet är NP-komplett visar denna minskning att beslutsversionen av det längsta vägen också är NP-komplett. I detta beslutsproblem är ingången ett diagram G och ett tal k ; den önskade utgången är "ja" om G innehåller en sökväg med k eller flera kanter, och nej annars.

Om det längsta vägproblemet kunde lösas på polynomtid kunde det användas för att lösa detta beslutsproblem genom att hitta en längsta väg och sedan jämföra dess längd med antalet  k . Därför är det längsta vägen problemet NP-hårt. Frågan "finns det en enkel väg i en given graf med åtminstone k kanter" är NP-komplett.

I viktade kompletta grafer med icke-negativa kantvikter är det viktade längsta banproblemet detsamma som Resande säljarens vägproblem , eftersom den längsta banan alltid innehåller alla hörn.

Acykliska grafer

En längsta väg mellan två givna hörn s och t i ett viktat diagram G är samma sak som en kortaste bana i en graf - G härledd från G genom att ändra varje vikt till dess negation. Därför, om kortaste vägar kan hittas i - G , då längsta banor kan också hittas i G .

För de flesta kurvor, är denna omvandling inte användbart eftersom det skapar cykler av negativ längd i - G . Men om G är en riktad acyklisk graf , kan inga negativa cykler skapas och en längsta väg i G kan hittas i linjär tid genom att tillämpa en linjär tidsalgoritm för kortaste vägar i - G , som också är en riktad acyklisk graf. För en DAG, kan den längsta vägen från en källa vertex till alla andra vertex erhållas genom att köra den kortaste vägsalgoritm på - G .

På samma sätt, för varje toppunkt v i en given DAG, kan längden på den längsta vägen som slutar vid v erhållas genom följande steg:

1. Hitta en topologisk ordning av den angivna DAG.
2. Beräkna längden på den längsta vägen som slutar vid v för varje toppunkt v i DAG genom att titta på dess inkommande grannar och lägga till en till den maximala längden som registrerats för dessa grannar. Om v inte har några inkommande grannar, ställ in längden på den längsta vägen som slutar på v till noll. I båda fallen registrerar du detta nummer så att senare steg i algoritmen kan komma åt det.

När detta väl har gjorts kan den längsta vägen i hela DAG erhållas genom att börja vid toppunkten v med det största registrerade värdet, sedan steg upprepade gånger bakåt till sin inkommande granne med det största registrerade värdet och vända sekvensen av hörn som finns i den här vägen.

Detta är ekvivalent med att köra den kortaste vägsalgoritm på - G .

Kritiska vägar

Den kritiska vägmetoden för schemaläggning av en uppsättning aktiviteter involverar konstruktionen av en riktad acyklisk graf där hörnpunkterna representerar projektets milstolpar och kanterna representerar aktiviteter som måste utföras efter en milstolpe och före en annan; varje kant viktas med en uppskattning av hur lång tid motsvarande aktivitet tar att fullborda. I en sådan graf är den längsta vägen från den första milstolpen till den sista den kritiska vägen, som beskriver den totala tiden för slutförandet av projektet.

De längsta banorna för riktade acykliska grafer kan också appliceras i skiktad grafritning : tilldelning av varje toppunkt v av en riktad acyklisk graf G till lagret vars antal är längden på den längsta banan som slutar vid v resulterar i en lagertilldelning för G med lägsta möjligt antal lager.

Approximation

Björklund, Husfeldt & Khanna (2004) skriver att det längsta vägproblemet i obevägda oriktade grafer "är ökänt för svårigheten att förstå dess approximationshårdhet". Den bästa approximationsalgoritmen för polynom som är känd för detta fall uppnår endast ett mycket svagt approximationsförhållande . För alla${\ displaystyle n / \ exp (\ Omega ({\ sqrt {\ log n}}))}$${\ displaystyle \ epsilon> 0}$,det är inte möjligt att approximera den längsta vägen till inom en faktor om NP inte ingår inom kvasipolynomisk deterministisk tid ; emellertid finns det ett stort gap mellan detta otillgängliga resultat och de kända approximationsalgoritmerna för detta problem. ${\ displaystyle 2 ^ {(\ log n) ^ {1- \ epsilon}}}$

När det gäller ovägda men riktade grafer är starka otillgängliga resultat kända. För varje problem kan inte approximeras till inom en faktor om inte P = NP, och med starkare komplexitetsteoretiska antaganden kan det inte approximeras inom en faktor av . Den färgkodning teknik kan användas för att hitta vägar logaritmisk längd, om de finns, men detta ger en approximation förhållande på bara . ${\ displaystyle \ epsilon> 0}$${\ displaystyle n ^ {1- \ epsilon}}$${\ displaystyle n / \ log ^ {2+ \ epsilon} n}$${\ displaystyle O (n / \ log n)}$

Parameteriserad komplexitet

Det längsta sökproblemet är fast parametrar som kan spåras när det parametreras efter längden på sökvägen. Till exempel kan den lösas i linjär tid i storleken på inmatningsdiagrammet (men exponentiellt i längden på banan) med en algoritm som utför följande steg:

1. Utför en djup-första sökning i diagrammet. Låt vara djupet i det resulterande sökdjupet för första djupet .${\ displaystyle d}$
2. Använd sekvensen av rot-till-blad-banor för det djup-första sökträdet, i den ordning som de passerade av sökningen, för att konstruera en kurvsnedbrytning av grafen med sökbredd .${\ displaystyle d}$
3. Tillämpa dynamisk programmering på denna vägnedbrytning för att hitta en längsta väg i tid , var är antalet hörn i diagrammet.${\ displaystyle O (d! 2 ^ {d} n)}$${\ displaystyle n}$

Eftersom utgångsbanan har en längd som är minst lika stor , begränsas körtiden också av , var är längden på den längsta banan. Med hjälp av färgkodning kan beroendet av banlängden reduceras till exponentiellt. En liknande dynamisk programmering teknik visar att den längsta banan problemet är också fast-parametern lätthanterlig när parametriseras av treewidth av grafen. ${\ displaystyle d}$${\ displaystyle O (\ ell! 2 ^ {\ ell} n)}$${\ displaystyle \ ell}$

För grafer med begränsad klickbredd kan den längsta vägen också lösas med en dynamisk programmeringsalgoritm för polynom. Exponenten för polynomet beror dock på grafens klickbredd, så dessa algoritmer är inte fasta med parametrar. Den längsta vägen problemet, parametreras genom klick-bredd, är svårt för den parametriserade komplexitet klassen , som visar att är en fast parameter lätthanterlig algoritmen osannolikt att existera. ${\ displaystyle W [1]}$

Särskilda klasser av grafer

En linjär tidsalgoritm för att hitta en längsta väg i ett träd föreslogs av Dijkstra på 1960-talet, medan ett formellt bevis på denna algoritm publicerades 2002. Dessutom kan en längsta väg beräknas i polynomtid på viktade träd, på blockdiagram på kaktusar på bipartita permutations grafer , och ptolemaiska grafer .

För klassen av intervalldiagram är en tidsalgoritm känd, som använder en dynamisk programmeringsmetod. Denna dynamiska programmeringsmetod har utnyttjats för att erhålla polynom-tidsalgoritmer på de större klasserna av cirkelbågsdiagram och samkomparabilitetsdiagram (dvs. komplementen till jämförbarhetsdiagram , som också innehåller permutationsdiagram ), båda har samma körtid . Den senare algoritmen är baserad på specialegenskaper för LDX-toppens ordning för sam-jämförbarhetsdiagram. För sam-jämförbarhetsdiagram är också en alternativ polynom-tidsalgoritm med högre körtid känd, som är baserad på Hasse-diagrammet för den delvis ordnade uppsättningen definierad av komplementet till ingångssam-jämförbarhetsdiagrammet. ${\ displaystyle O (n ^ {4})}$${\ displaystyle O (n ^ {4})}$${\ displaystyle O (n ^ {7})}$

Dessutom är det längsta vägproblemet löst på polynomtid i någon klass av grafer med avgränsad trebredd eller avgränsad klickbredd, såsom avstånds-ärftliga grafer . Slutligen är det tydligt NP-svårt på alla grafklasser där Hamiltonian-vägproblemet är NP-svårt, till exempel på delade grafer , cirkeldiagram och plana grafer .

En enkel modell av en riktad acyklisk graf är Prismodellen , utvecklad av Derek J. de Solla Price för att representera citatnätverk . Detta är tillräckligt enkelt för att analysresultat ska kunna hittas för vissa fastigheter. Till exempel skalas längden på den längsta sökvägen från den n: a noden som läggs till nätverket till den första noden i nätverket som . ${\ displaystyle \ ln (n)}$

Se även

• Sats Gallai – Hasse – Roy – Vitaver , en dualitetsrelation mellan längsta banor och graffärgning
• Längsta okrossade riddarens väg
• Snake-in-the-box , den längsta inducerade vägen i en hyperkubgraf
• Prismodell , en enkel citeringsnätverksmodell där de längsta banlängderna kan hittas analytiskt

Referenser

externa länkar

• " Find the Longest Path ", sång av Dan Barrett