13 December 2021

As the first Dane, Professor Mikkel Thorup receives the prestigious Fulkerson Prize

Algorithms

The Fulkerson Prize goes to the most famous research results in discrete mathematics, which is the branch of mathematics most relevant to computer science and data science. Professor Mikkel Thorup is the first Dane ever to be awarded the prize for finding the solution to a problem that it took him 18 years to figure out.

Professor Mikkel Thorup
Mikkel Thorup is one of the world's leading experts in algorithms and data structures.

It takes time, perseverance, and patience to solve the kind of mathematical problems that algorithmics deals with – and preferably change of air along the way.

- It's like hiking an unknown mountain terrain. You may have an idea of ​​a possible path to a particular peak, but then the path turns out to be cut off by deep ravines. While you are out there, you must constantly be creative and seek new paths. You must also be flexible because you often discover other peaks that are worth visiting, says Professor Mikkel Thorup. 

The problem he has solved is about edge connectivity of a network which is one of the most fundamental problems of graph theory. It's about figuring out how many edges you can remove from a network before it breaks.

After 15 years in the United States, a move back to Denmark, and finally a trip to Japan, where Mikkel Thorup visited the Japanese co-author, Professor Ken-Ichi Kawarabayashi, and took countless walks around the Imperial Palace in Tokyo, the big breakthrough came:

An efficient algorithm that finds the edge connectivity of a network completely without the use of randomness; that is, an algorithm that can guarantee its answers one hundred percent. The result was published in 2018 in the Journal of the ACM.

- During my 15 years as a leading industrial researcher at AT&T Laboratories, the solution to this problem was always at the top of my wish list. Networks exist in all sorts of places, for example as road networks and social media. When you have a large network, you want an efficient algorithm that can quickly figure out the edge connectivity; that is, how close the network is to breaking down, Mikkel Thorup explains. 

Long-lasting influence on the field

The problem of edge connectivity has been researched since 1961. Mikkel Thorup himself became interested in the problem when he was a visiting researcher at the Massachusetts Institute of Technology (MIT) in 1997.

A famous professor from MIT, David Karger, had in 1996 presented an effective solution to the problem, but his breakthrough was a randomized algorithm that uses randomness. This means that one can never be one hundred percent sure whether Karger's algorithm gives the correct answer.

Although Karger's algorithm says that the network is well connected, it may be about to fall apart. Karger's big unsolved problem was to find an efficient algorithm that did not use randomness so that one can rely one hundred percent on the answer.

The American Mathematical Society (AMS), which is the world's largest mathematics community and is responsible for awarding the Fulkerson Prize together with the Mathematical Optimization Society (MOS), writes the following about Mikkel Thorup's and Ken-Ichi Kawarabayashi's solution:

- This work does not just improve the running time of the algorithm, impressive as that is. Its main contributions are conceptual: the paper introduces powerful and impactful new ideas that will have a long-lasting influence on the field.

Read the full statement from AMS here.

Mikkel Thorup and Ken-Ichi Kawarabayashi's theoretical breakthrough has inspired further research in the field, and in December 2021 the article had already been cited 87 times.

 

 

 

 

 

 

Contact

Mikkel Thorup
Professor, Department of Computer Science
Head of the Algorithms and Complexity section and Head of the BARC centre
mthorup@di.ku.dk

Caroline Wistoft
Communications consultant, Department of Computer Science
cawi@di.ku.dk

More stories