Eva Rotenberg and her partner from KU found a back door into a theoretical machine room to handle changes in a network. The working method contributes to her future research.
Researchers who experience a scientific breakthrough often describe how in the time to come they are filled with a mixture of happiness, energy, and insomnia because they think at the research result all the time, and it has to be verified and published.
This was also the case for Computer Scientist and Associate Professor Eva Rotenberg from the section Algorithms, Logic and Graphs (AlgoLoG) at DTU Compute and her partner, Computer Scientist and Assistant Professor at the University of Copenhagen Jacob Holm. By thinking untraditionally, they solved one of the most fundamental puzzles in the field of graph theory, where they developed an algorithm to quickly answer what happens when a graph changes.
The research result was announced last year, and is so remarkable that Eva Rotenberg and Jacob Holm will talk about it next week at the prestigious conference ‘Highlights of Algorithms’. The conference only invites researchers behind the world's most important achievements in algorithmics.
“I hope that our result can be an inspiration to other researchers to take a step back and ask the slightly more theoretical questions, such as how much a solution should change when the question changes a little bit because it can lead to some effective programs. It is a technique that I myself will use in the future,” says Eva Rotenberg.
Network changes
Graph theory plays a fundamental role in computer science, especially in the design and analysis of algorithms. Graphs consist of nodes (points) connected by edges (connecting lines). For example, graphs are used for modeling networks, modeling the structure of computer software, and visualizing the command stream in an application. But graph theory can in principle be about all kinds of networks; road networks, infection networks, transport networks, communication networks.
"I hope that our result can be an inspiration to other researchers to take a step back and ask the slightly more theoretical questions, such as how much a solution should change when the question changes a little bit. "
Eva Rotenberg, Computer Scientist and Associate Professor from the section Algorithms, Logic and Graphs (AlgoLoG) at DTU Compute
In the physical world, networks change over time. In some places, it can be extra important to know if connections cross each other. On printed circuit boards and in microchips, it will e.g. lead to a short circuit.
Changes in such dynamic graphs have been causing problems for mathematicians for many years. Efforts have been made to effectively update whether a graph can still be drawn without the lines intersecting when connections disappear and new ones emerge.
Eva Rotenberg and Jacob Holm have developed an algorithm to handle changes in the network so that one either avoids that the connection lines cross each other or must conclude that the graph can not be drawn.
“You can not just calculate something static on a network, but must be able to include dynamic changes in the calculations. We have found out how, on a theoretical level, you can quickly and efficiently handle a change in a graph, so that the nodes can be connected if possible, without the connecting lines crossing each other, ”says Eva Rotenberg.
"The challenge is to distinguish between the situation where the graph can no longer be drawn without a cross, and the situation where you just have to change the drawing to make room for the new connection."
Take a step back
The researchers chose to approach the task more theoretically than usual. Instead of going directly into solving the algorithmic problem itself - whether the updated graph can be drawn without the lines crossing - they studied the properties of the network. In this way, they would investigate whether there could be a smart way to draw the network, so that regardless of which new connection line came up, one could just make quite small / few changes to the drawing.
"The way to solve the problem was actually to take a step back and be even more nerdy and just look at the number of changes that were needed. When we answered that question first, we found in that answer the key to solving the problem with a fast efficient algorithm almost by chance, as by finding a back door in,” explains Eva Rotenberg.
"If you ask a question and I answer it and you change your question a little bit, how much do I have to change my answer? Similarly in graph theory, where you can change your solution quite a bit when the question changes quite a bit. I take that way of thinking with me as an important question. ”
While the working method for solving theoretical mathematical problems can be used right now, Eva Rotenberg is less concerned with how the result can be used.
“I am not specialized in getting the theoretical results to benefit the world. There are others who do that. I take care of the ground research - the theoretical. We have a network and we do not know if it is a transport network or a network between people. We just know there are nodes and edges. And then we make our algorithms so that they work in general for networks. ”
In January 2021, Eva Rotenberg received a Villum Young Investigators grant of six million Danish kroner to employ two PhD students and a postdoc in the project Efficient Recomputations for Changeful Problems, where they will be researching dynamic graphs.
1913 model with three houses: A well-known example of graph theory ‘The Three Utilities Problem’ dates back to 1913. The Strand Magazine presented readers with a task in which three huts were to supply water, gas, and electricity, but no ‘supply lines’ between the houses were to cross each other. On paper (2D) it is impossible to solve the task: Wikipedia CC BY-SA 4.0. 4.0