I oppgave e fra høsteksamen 2012 står det: «I læreboka … argumenteres det for at det er meningsløst å tillate negative sykler i korteste veier. Hvis vi begrenser oss til å kun lete etter korteste veier uten sykler (såkalte simple paths), hvorfor er det likevel problematisk om grafen vår inneholder negative sykler (som kan nås fra startnoden)?»

Et spørsmål fra en student om dette lød omtrent som følger:

Hvorfor er problemet NP-hardt?

Jeg fant et svar som sier at man kan redusere fra longest simple path: «This can be reduced from the longest-path problem. If there were a fast solver for your problem, then given a graph with only positive edge-weights, negating all the edge-weights and running your solver would give the longest path in the original graph.»

Men er ikke dette det samme som å løse et vanlig shortest path og så gjøre alle kanter negative for så å kunne løse longest path problem?

Svar på Piazza i 2013:

Disse tingene kan være litt intrikate, og det handler ofte om detaljer…

Det generelle korteste-vei-problemet (med vilkårlige vekter) er NP-hardt fordi man kan redusere fra lengste-vei-problemet, som er NP-hardt. Hvis vi f.eks. forbyr negative sykler (eller negative vekter, eller sykler generelt), så fungerer ikke denne reduksjonen lenger. I flere av disse tilfellene har vi effektive algoritmer, som dem du har lært i faget. (Teknisk sett vet vi jo ikke om problemet fortsatt er NP-hardt, siden vi ikke vet om P = NP, men vi har i hvert fall ikke lenger noe bevis for at det er NP-hardt – og vi har algoritmer for å løse problemet.)

Hvordan ser vi at lengste-vei-problemet er NP-hardt? Vi kan f.eks. redusere fra Hamilton-sykel-problemet (med noen små justeringer; ser du hvordan?-)

Så spør du om lengste vei ikke er det samme som å finne korteste vei der alle kantene skifter fortegn – og det er det. Det er det som er den mest opplagte reduksjonen for å vise at også korteste-vei-problemet er NP-hardt, dvs., de to problemene er ekvivalente.

Men det er altså bare de generelle problemene som er (eller som vi vet at er) NP-harde. F.eks. er korteste vei uten negative sykler og (helt ekvivalent) lengste vei uten positive sykler lett å løse. I svaret du siterer beskriver de jo en variant av problemet der det ikke er noe forbud mot positive sykler i lengste-vei-varianten eller negative sykler i korteste-vei-varianten. Siden de kun tillater positive (resp. negative) vekter, så ville jo en slik graf være asyklisk (og i asykliske grafer finner vi lett både korteste og lengste vei, uavhengig av fortegn på kantvekter).

Tillegg, 2018

Et viktig poeng her er hvorvidt forbudet mot sykler er i input-grafen eller i svaret. Hvis vi forbyr det i input-grafen, så har vi en DAG, og der kan vi lett finne lengste eller korteste vei. Dersom vi derimot har en vilkårlig (vektet, rettet) graf der vi skal finne korteste vei, og vi forbyr sykler i svaret, så er det en annen sak. Det er nemlig det vi gjør, i den vanlige formuleringen av problemet – og det å finne en slik sti er altså NP-hardt om grafen har negative sykler vi kan snuble borti, selv om disse syklene ikke får lov til å være med i et gyldig svar.