Mathematical riddle dating back decades finally solved after being lost and found by researchers

Two Danish computer scientists solved a long-standing mathematical puzzle that had been dormant for decades, after researchers had failed to make substantial progress since the 1990s.

The abstract problem in question is part of what is called graph theory, and specifically concerns the challenge of finding an algorithm to solve the flatness of a dynamic graph. It might sound a little intimidating, so if your graph theory is a little rusty, there’s a much more fun and accessible way to think about the same ideas inherent.

Going back as far as 1913 – although mathematical concepts can probably go back much further – a puzzle called the Three Utility Problem has been published.

Simply put, imagine there are three houses lined up in a row, which you could draw on a piece of paper. Below you can also draw three separate utilities: water, gas and electricity.

Solution of three utilities with a line crossing. (CMG Lee / Wikimedia Commons / CC BY-SA 4.0)

The challenge is to draw lines on this simple graph, connecting the three utilities to each house. But there is one problem: none of the lines (nine in total) on the paper can intersect. Can you think of a way to bring everything together without any of the connections crossing?

In the most conventional sense – on a plain two-dimensional sheet of paper, as an example of a planar graph – it is not possible to solve the three-utility problem. Although it may be impractical, not all of these houses can receive their connections.

But the three utilities problem is not so much a puzzle to be solved, but rather an example of how some types of graph networks are not planar – that is, capable of having edges. (lines) connecting their different summits (houses and utilities) without the lines being crossed.

When dealing with more complex graphs that involve more vertices, Kuratowski’s theorem helps mathematicians determine whether graphs are plane or not, and since the 1970s, researchers have also designed algorithms to do the same. faster.

However, after a last algorithmic advance in the 1990s, no substantial progress has been made in this area for decades, at least not with regard to algorithms capable of solving dynamic (changing) graphs.

Fast forward to last year, and computer scientists Jacob Holm from the University of Copenhagen and Eva Rotenberg from the Technical University of Denmark were tackling the problem.

“We almost gave up on getting the last piece and solving the puzzle,” says Holm. “We guessed that it would take another five years of work, at best, before we could solve the puzzle.”

It was then, almost by accident, that they realized that they had indeed already solved most of the problem in another research – a pre-print article on related planar concepts, which the pair had. published online in 2019.

With the hidden solution already published, the pair fell out in the following weeks, writing formal proof of their improvement in the graphing algorithm, which had not been improved since the 1990s.

“We worked tirelessly on the article, for five to six weeks. And it ended up filling over 80 pages, ”Rotenberg explains.

The results, now published, provide an algorithm that takes the least computation time to resolve the question of whether a dynamic graph – subjected to insertions and deletions of edges connecting its vertices – can support planar embedding. (Simply put, if it could be drawn on a piece of paper with no crossed lines.)

This is a big step forward, as the same difficulties present in something as conceptually simple as the three utilities problem become much more unfathomable in areas like microchip design or road planning, where much more. of tops are involved as just three houses and three utilities.

“It turns out that for dynamic graph problems it is often possible to create a data structure that can be used to recalculate the response after each graph change much faster than recalculating the response from scratch,” explains Holms.

“This result is of course a huge personal victory for us.”

The results are reported in STOC 2020: Proceedings of the 52nd ACM SIGACT Annual Symposium on Computing Theory.