Problemet med den längsta vägen

Det längsta vägproblemet är problemet med att hitta en enkel väg med maximal längd i en given graf. En bana kallas enkel om den inte har några upprepade hörn. Längden på en bana kan mätas antingen genom antalet kanter eller (i fallet med viktade grafer ) genom summan av vikterna av dess kanter. Till skillnad från problemet med kortaste vägen , som kan lösas i polynomtid på grafer utan negativa viktcykler, är problemet med den längsta vägen NP-hårt och kan inte lösas i polynomtid för godtyckliga grafer, om inte P = NP . Att tillhöra en tyngre komplexitetsklass gör också att problemet är svårt att approximera. Emellertid löses problemet i linjär tid på riktade acykliska grafer , som har viktiga tillämpningar i kritiska vägproblem vid schemaläggningsproblem.

NP-svårighet

NP-hårdheten för det ovägda problemet att hitta den längsta vägen kan visas genom att reducera problemet till att hitta en Hamiltonsk väg — en graf G har en Hamiltonsk väg om och bara om den längsta vägen i den har längden n  − 1 , där n är antalet grafens hörn G. _ Eftersom problemet med att hitta en Hamiltonsk väg är NP-komplett visar denna reduktion att problemet med att hitta den längsta vägen i det lösbara fallet också är NP-komplett. I detta lösbarhetsproblem är inmatningen en graf G och ett tal k . Den förväntade utsignalen är "ja" om G innehåller en väg med k eller fler bågar, eller inte på annat sätt [1] .

Om problemet med att hitta den längsta vägen kunde lösas i polynomtid skulle det kunna användas för att lösa detta lösbarhetsproblem genom att hitta den längsta vägen och jämföra längden på den resulterande vägen med talet k . Således är problemet med att hitta den längsta vägen NP-hårt. Det är inte NP-komplett eftersom det inte är ett lösbarhetsproblem [2] .

I viktade kompletta grafer med icke-negativa kantvikter är problemet med att hitta den vägda längsta vägen samma problem som problemet med resande säljare , eftersom den längsta vägen alltid inkluderar alla hörn av detta problem [3] .

Acykliska grafer och kritiska vägar

Den längsta vägen A mellan två givna hörn s och t i en viktad graf G är densamma som den kortaste vägen i grafen − G som erhålls från G genom att ändra alla vikter till vikter med motsatt tecken. Således, om den kortaste vägen kan hittas i − G , så kan den längsta vägen i G [4] också hittas .

För de flesta grafer är denna transformation värdelös, eftersom den skapar cykler med negativ längd i − G . Men om G är en riktad acyklisk graf är det omöjligt att skapa en negativ cykel och den längsta vägen i G kan hittas i linjär tid genom att tillämpa den kortaste vägalgoritmen i − G (även en riktad acyklisk graf) som löper i linjär tid [4] . Till exempel, för alla hörn v i en riktad acyklisk graf, kan längden på den längsta vägen som slutar på v erhållas genom att utföra följande steg:

  1. Vi utför topologisk sortering av den givna riktade acykliska grafen (OAG).
  2. För varje vertex v av OAG i en topologisk sortering, beräknar vi längden på den längsta vägen som slutar vid vertex v genom att titta på de inkommande bågarna från grannarna och lägga till en till den maximala längden i posterna för dessa grannar. Om v inte har några inkommande bågar, ställ in längden på den längsta vägen som slutar på v till noll.

När detta är gjort kan den längsta vägen i hela grafen erhållas genom att börja vid vertex v med det största registrerade värdet och arbeta baklänges, välja den inkommande båge vars startpunktsingång har det största värdet.

Den kritiska vägmetoden för att schemalägga en uppsättning aktiviteter använder konstruktionen av en riktad acyklisk graf där hörnen representerar projektets nodalhändelser, och bågarna representerar det arbete som ska utföras före och efter nodalhändelsen. Varje båge tilldelas en vikt som är lika med den beräknade tiden för att slutföra arbetet. I en sådan graf är den längsta vägen från den första nodalhändelsen till den sista den kritiska vägen, som bestämmer den totala slutförandetiden för projektet [4] .

Den längsta vägen av riktade acykliska grafer kan också användas för lager-för- lager-ritning av grafer - vi placerar varje vertex v i en riktad acyklisk graf G på en nivå vars nummer motsvarar längden på den längsta vägen som slutar på v . Som ett resultat får vi arrangemanget av hörn efter nivåer, där antalet nivåer kommer att vara minimalt [5] .

Approximation

Bjorklund, Hasfeldt och Kanna skrev att problemet med att hitta den längsta vägen i en oviktad oriktad graf är "ökänt för sin svårighet att förstå sin approximationssvårighet" [6] . Den mest kända approximationsalgoritmen för polynom körtid ger endast en mycket svag approximation, [7] . Det är inte möjligt för någon att approximera den längsta vägen med en faktor som är mindre än , om inte NP tillhör kvasi-polynomial deterministiska tidsproblem . Det finns dock ett stort gap mellan detta approximationsresultat och kända approximationsalgoritmer för detta problem [8] .

När det gäller ovägda men riktade grafer finns det välkända starka approximerbarhetsresultat. För någon kan problemet inte approximeras inom , om inte P = NP, och under starka teoretiska antaganden kan problemet inte approximeras inom [6] . Du kan använda färgkodningstekniken för att hitta en logaritmisk längdväg om den finns, men denna teknik ger bara en approximationsfaktor [9] .

Parameteriserad komplexitet

Problemet med att hitta den längsta vägen är fast-parametriskt lösbar om den parametriseras av vägens längd. Till exempel kan problemet lösas i tid som är linjär i storleken på ingångsgrafen (men i exponentiell tid i vägens längd) med en algoritm som tar följande steg:

  1. Vi gör en djupsökning på grafen. Låt vara djupet av det resulterande sökträdet djupt in i .
  2. Vi använder banorna från roten till bladen på sökträdet på djupet i den ordning som de söks i, i motsats till bandiagramsnedbrytning med pathwidth .
  3. Vi använder dynamisk programmering för denna vägnedbrytning för att hitta den längsta vägen i tiden , där är antalet grafens hörn.

Eftersom utgångsvägen har en längd på minst , kommer körtiden också att begränsas av , där är längden på den längsta banan [10] . Med hjälp av färgkodning kan banlängdsberoendet reduceras till en enda exponentiell [11] [12] [13] . En liknande dynamisk programmeringsteknik visar att problemet med den längsta vägen också är fast-parametriskt lösbart i grafens trädbredd .

För grafer med begränsad klickbredd kan det längsta vägproblemet lösas i polynomtid med hjälp av en dynamisk programmeringsalgoritm. Graden av polynomet beror dock på klickbredden på grafen, så dessa algoritmer kan inte avgöras med fasta parametrar. Uppgiften att hitta den längsta vägen parametriserad av klickbredd är svår för klassen parametriserad komplexitet , vilket innebär att det knappast finns en fast-parametrisk lösbar algoritm [14] .

Särskilda fall av grafer

Det längsta vägproblemet kan lösas i polynomtid på komplementen av jämförbarhetsgrafer [15] . Det kan också lösas i polynomtid på valfri klass av grafer med avgränsad trädbredd eller avgränsad klickbredd, såsom avståndsärvda grafer . Problemet är dock NP-svårt, även om vi begränsar oss till delade grafer , cirkelgrafer eller plana grafer [16] .

Se även

Anteckningar

  1. ↑ Schrijver, 2003 , sid. 114.
  2. ↑ Cormen, Leiserson, Rivest, Stein, 2001 , sid. 978.
  3. ↑ Lawler, 2001 , sid. 64.
  4. ↑ 1 2 3 Sedgewick, Wayne, 2011 , sid. 661–666.
  5. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , sid. 265–302.
  6. ↑ 1 2 Björklund, Husfeldt, Khanna, 2004 , sid. 222–233.
  7. ↑ ( Gabow, Nie 2008 ). För tidigare arbete, även med en svagare approximation, se artiklarna av Gabow ( Gabow 2007 ) och Björklund och Hasfeldt ( Björklund, Husfeldt 2003 ).
  8. ↑ Karger, Motwani & Ramkumar, 1997 , sid. 82–98.
  9. ↑ Alon, Yuster, Zwick, 1995 .
  10. ↑ ( Bodlaender 1993 ). För en tidigare fast-parameter avgörbar algoritm med något bättre beroende av väglängd men sämre beroende av graflängd, se Monien 1985 .
  11. ↑ Chen, Lu, Sze, Zhang, 2007 , sid. 298-307.
  12. ↑ Koutis, 2008 , sid. 575-586.
  13. ↑ Williams, 2009 , sid. 315-318.
  14. ↑ Fomin, Golovach, Lokshtanov, Saurabh, 2009 , sid. 825–834.
  15. ↑ ( Ioannidou och Nikolopoulos 2011 ). För tidigare arbete om mer begränsade klasser, se ( Ioannidou, Mertzios, Nikolopoulos 2011 ) och ( Uehara, Valiente 2007 ).
  16. ↑ Ioannidou, Mertzios, Nikolopoulos, 2011 .

Litteratur

Länkar