Shortest paths in networks that change over time
Finding the best route from a starting point to a destination in a network is an important problem in practice and most of us frequently rely on computers to solve it.
We ask Rejseplanen, the GPS navigation unit in our car, or some other software to guide us to our destination in hopefully the best possible way. Here "best"' typically means "shortest" or "fastest". However, road networks are not static and what is currently the best route may suddenly become slow due to heavy traffic or may even become infeasible due to road construction.
The problem that route planning software solves is called the shortest path problem. This is a classical algorithmic problem dating back to the 1950s. Shortest path algorithms use an abstract representation of the network called a graph, consisting of edges (representing segments of roads) and vertices (representing points where such road segments end, for instance in road crossings). Each edge has an associated weight representing the cost of traversing it (this could be travel time in a car) and the edge may have a direction if it represents a one-way street.
The very abstract graph representation of a network has a major advantage, namely that it can be used to represent not just roadmaps but all types of networks such as the internet, the human brain, and the network of friend relations on Facebook. This often makes graph algorithms very powerful due to their many applications.
A graph is called dynamic if it can change over time. For instance, removing an edge may correspond to a part of the road network currently being inaccessible due to road construction.
Traditional algorithms for the shortest path problem assume the graph to be static as opposed to dynamic, not a valid assumption for most networks in the real world. Such algorithms can still be used in the dynamic setting by simply rerunning them whenever a change to the graph has occurred. Intuitively, this is very wasteful if the change to the graph is small (say, the removal of a single edge) since most of the graph remains the same. In more recent years, shortest path algorithms have been developed that exploit this fact. Such algorithms can handle changes to the graph much faster than the more naive approach of rerunning from scratch after each change.
An important version of the problem is called the decremental single-source shortest path problem. This version has been studied for decades and it appears as a subproblem in a number of other settings. Sticking with the road network example, the problem is to maintain shortest paths from a single starting point to all possible destinations when updates to the road network represent either more traffic (an increase in the weight of an edge) or a part of a road being blocked (an edge being removed).
BARC researcher Christian Wulff-Nilsen, together with former BARC colleague Maximilian Probst Gutenberg and Aaron Bernstein from Rutgers University, have managed to obtain an essentially optimal algorithm for this problem. What this roughly means is that any algorithm developed in the future for this problem is no faster than the new algorithm when the running time is expressed as a function of the number of vertices of the dynamic graph. The new result was presented recently in a paper at FOCS 2020.
A key technical contribution of the paper is a new way to represent the graph so that it shares important properties with a directed acyclic graph, a much simpler graph to work with for which there is an essentially optimal algorithm. The paper then shows how to modify the algorithm to work with this representation without slowing it down. The new technique is quite general and the hope is that can be applicable to a range of other dynamic shortest path problems.
Further reading:
Near-Optimal Decremental SSSP in Dense Weighted Digraphs, https://arxiv.org/abs/2004.04496 , arXiv.