Researchers almost blurted out the solution to a mathematical conundrum

Computer researchers at the University of Copenhagen and the Technical University of Denmark (DTU) thought they were five years away from solving a mathematical puzzle from the 1980s. In fact, and without knowing it, they had almost solved the problem and had just unveiled much of the solution in a research article. The solution could be used to improve the phones and computers of tomorrow.

Jacob Holm and Eva Rotenberg

A real puzzle. This is how we can safely describe this mathematical problem in the discipline of graph theory. Two mathematicians from the Department of Computer Science and DTU at the University of Copenhagen have now solved a problem the world’s fastest and smartest have struggled with since the 1980s.

The two computer scientists, Assistant Professor Jacob Holm from UCPH and Associate Professor Eva Rotenberg from DTU almost gave their solution in the summer of 2019, after submitting a research article that became the precursor to the article in which they finally solved the mathematical puzzle.

“We had almost given up on getting the last piece and solving the puzzle. We thought we got a minor, interesting result, but by no means solved the problem. We guessed that there would be another five years of work, better, before we could solve the riddle, ”says Jacob Holm, who is with BARC, the algorithm section of the computer science department at UCPH.

The three utilities problem

In 1913, a forerunner of the now-solved mathematical puzzle was published in Strand magazine like “The Three Utilities Problem”. It made the magazine’s readers scratch their heads and think. In the problem, each of the three cabins must have water, gas and electricity, while the “lines” between the houses and water, electricity and gas may not intersect. which is not possible.

A solution between the lines

Simply put, the puzzle is how to connect a number of points in a graph without allowing the lines that connect them to intersect. And how, with a mathematical calculation – an algorithm – you can make changes to a vast “network of graphs” to ensure that no line intersects without having to start over. Properties that can be used, among other things, to build huge road networks or the tiny guts of computers, where electrical circuits on circuit boards cannot intersect.

Jacob Holm has been interested in the mathematical puzzle since 1998, but the answer was only revealed while the two researchers read their previously submitted research paper. Meanwhile, the researchers have heard of a new mathematical technique that they believe could be applied to the problem.

“As we read our research article, we suddenly realized that the solution was before our eyes. Our next reaction was, “Oh no, we shot ourselves in the foot and gave the solution,” says Associate Professor Eva Rotenberg of DTU.

About graph theory

A graph is a very simple construction used to model things that can be described as objects and the connections between them. Graph theory is both a field of mathematics and an important tool in computer science.

In this context, a graph can be illustrated by a diagram made up of a certain number of points (nodes, vertices) associated with a certain number of lines (edges). Each edge is shown as a line (or a curved part) with nodes as two ends.

About the solution

There are two types of updates in dynamic charts: one can remove an edge and you can insert a new edge. These two operations must be performed by the user, while an algorithm follows the network design at all times. This is the algorithm for which the researchers found the recipe.

Can be used for computer electronics

It was at this point that the two researchers got busy writing the research paper and working out the details to solve the riddle that Holm had been working on intermittently since 1998.

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

Fortunately, no one beat them to the solution and the two researchers were able to present their results at the main theoretical computer conferences, which were to be held in Chicago, but which ended up being held virtually.

So, what can the solution to this mathematical puzzle be for? The two researchers aren’t sure, but they have a few suggestions.

“Our research is basic research, so we rarely know what it will be used for. Even from the start we find applications that are difficult to imagine, ”says Jacob Holm, who adds:“ The design of chips and printed circuits, has found in all electronics, this could be an area where our result ends up being used. When you draw wires on a printed circuit board, they should never cross. Otherwise, short circuits will occur. The same goes for chips, which contain millions of transistors and for which you must have a graphic design. ”