Diverting Networks with Odd Paths

Abstract

Problemet Kortest Odde Sti er å finne en sti fra en node til en annen i en graf, der antall kanter i stier må være et oddetall. Selv om problemet virker som kun intet annet enn en kuriøsitet, er verdien i det at mange nyttigere problemer er enklere å løse om vi allerede vet hvordan vi løser Kortest Odde Sti.

Et av disse problemene er Nettverksomledning: gitt en graf, to noder og en markert kant, finn den billigste mengden med kanter slik at om de slettes fra grafen må alle stier fra den ene noden til den andre gå igjennom den markerte kanten. Mange av varientene til Nettverksomledning er NP-komplette, men kompleksiteten på planare grafer er ennå et åpent problem.

Vi implementerer en effektiv algoritme basert på Derigs' algoritme for å løse Korteste Odde Sti i urettede grafer, og bruker det til å implementere den første effektive algoritmen for Nettverksomledning på planare grafer.

The problem of Shortest Odd Path is to find a path from one vertex to another in a graph, where the number of edges in the path must be odd. Although the problem might seem a mere curiosity, its utility lies in being applicable to many more useful problems that are easier if we know how to solve Shortest Odd Path.

One of these problems is Network Diversion: given a graph, two vertices and a marked edge, compute the cheapest set of edges to delete from the graph such that all paths from one vertex to another must pass through the marked edge. Many of its variants are NP-complete, but its complexity on planar graphs remains an open problem.

We implement an efficient algorithm based on Derigs' algorithm to solve Shortest Odd Path on undirected graphs, and use that to implement the first-ever efficient algorithm for Network Diversion on planar graphs.