What is network flow algorithm?
A network in computer science theory can be simply understood as a system of nodes and the lines that connect them. The goal of a network flow algorithm is to find a way to move the maximum amount of goods or data from one point to another while keeping the cost as low as possible. This is like trying to find a way to transport a certain amount of goods from Copenhagen to Milan through the European transport system in a way that is both fast and cheap. The team’s algorithm can calculate this very quickly, as soon as the computer receives data about the network.
Overcoming the big computational challenge
Before the invention of Rasmus Kyng and his team, no one could calculate this fast. The problem of optimal computation for large networks has been a challenge for scientists for 90 years. Previously, the computation was always much slower than the speed at which the network collected data. And as the network became more complex, the computation time also increased disproportionately. This led to network problems becoming too large to be computed in real time.
Speed on par with network scale
Kyng’s team solved this problem. Their algorithm allows the computation speed to scale with the size of the network. This means that no matter how large the network gets, the computation time will only increase as if you were climbing a mountain at a constant speed, regardless of how complex the terrain is.
Before 2000, no algorithm could compute faster than a time proportional to the number of connections (denoted by m) in the network. By 2004, the computation time had dropped to m^1.33. But with Kyng’s algorithm, the additional computation time after reading the network data is almost negligible.
Like Porsche and horse carriage
Professor Daniel A. Spielman of Yale University, a teacher and colleague of Kyng, likened the new algorithm to the speed of a Porsche outrunning a horse-drawn carriage. Their algorithm, dubbed a “near-linear time algorithm,” has taken the theoretical computer science community by surprise. Kyng and his team’s algorithm even won the “Best Paper Award” at the 2022 IEEE Conference on Computer Science and was listed by the renowned science magazine Quanta as one of the top 10 important discoveries in computer science in 2022.
Ultra-fast computation for dynamic networks
The team’s original algorithm focused only on static networks, where connections do not change. However, they have further developed the algorithm to be able to calculate optimal flows for networks that change over time, such as those in biological networks, or social networks.
In June 2024, team member Simon Meierhans presented a new algorithm at the ACM Symposium on Theory of Computation (STOC) that solves the minimum-cost flow problem for networks that change gradually as new connections are added.
One practical application for network changes is the transportation network in Switzerland. When a route is closed, such as the Gotthard tunnel, which was partially closed after a landslide in 2023, Kyng’s algorithm can calculate the fastest alternative route between Milan and Copenhagen.
What makes Kyng’s algorithm special?
All computational methods must analyze the network over multiple iterations to find the optimal flow and lowest cost. Previous algorithms have had to choose between two main approaches: one that computes a portion of the network in its entirety over each iteration, or one that computes the entire network but uses average values to speed things up.
Kyng’s algorithm combines the best of both worlds. Instead of computing the entire network at once, they perform multiple smaller steps, each of which takes less resources but adds up to be much faster than a large computation.
From railways to the power grid
One of the greatest successes in this area in the past was the algorithm developed by Lester R. Ford Jr. and Delbert R. Fulkerson in the 1950s, which solved the maximum flow problem in a network. This algorithm seeks to move the most goods through the network without exceeding the capacity of the routes.
But in 2004, mathematicians like Daniel Spielman and Shang-Hua Teng created algorithms that could solve the minimum-cost problem faster by shifting the perspective from a rail network to an electrical network. On a power network, electricity can be split and flow through different connections, something trains can’t do. This shift was a game-changer in how we do calculations.
The shift in calculation principles
Kyng’s team not only developed new algorithms, but also created new mathematical tools to optimize their speed. They invented a data structure that organizes the network more efficiently, allowing changes in network connectivity to be detected very quickly. This significantly speeds up the computation process.
Their near-linear time algorithms not only solve large problems efficiently, but also change the way computers handle complex tasks. With a wide range of potential applications, these algorithms will continue to make breakthroughs in the future.
Note:
- Network flow algorithm : An algorithm that helps calculate the optimal flow in a network, to transport goods or data from one point to another at the lowest cost.
- Almost-linear-time algorithms : These are algorithms whose execution time is almost directly proportional to the network size, allowing large networks to be processed in a short time.
- Maximum flow problem : The problem of finding a way to move as much goods as possible through the network without exceeding the capacity of the routes.
Scientific report
“Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow” by Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans and Maximilian Probst Gutenberg, 11 June 2024, STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing. DOI: 10.1145/3618260.3649745