Social networks, transport networks and even models in artificial intelligence can be described mathematically as graphs: in such graphs, vertices represent, for example, people, places or computing units, whilst edges represent the connections between them. In many applications, however, such a network changes over time – for example, in transport planning, social media or AI models. Mathematicians at TU Bergakademie Freiberg have now developed a new approach to better understand these temporal graphs. PhD student Will J. Turner is now presenting his work at the ACM Symposium on Theory of Computing (STOC) — one of the world’s two leading conferences in theoretical computer science.
“To capture such changes, we look not just at a single graph, but at an entire sequence of graphs. Such time-dependent structures are called temporal graphs,” says Professor Johannes Carmesin, supervisor of Will Turner’s PhD TU Bergakademie Freiberg.
At the heart of the research lies a fundamental question: when can a sequence of networks be plotted in such a way that the individual representations align with one another over time? In the case of a single network, this question is closely linked to classical graph theory. With temporal graphs, it becomes significantly more difficult because the connections between the individual time steps can change: “You can think of it as a series of maps of the same transport network, taken at different points in time,” explains Professor Johannes Carmesin. “We want to understand when these maps fit together in such a way that the changes in the network can be represented consistently.”
Applying graph minor theory to time-dependent networks
The new work utilises methods from what is known as graph minor theory. This field investigates how large and complex graphs can be reduced to smaller basic structures. The two researchers from TU Bergakademie Freiberg are now applying this approach to time-dependent networks. For doubly connected temporal graphs, they provide a complete structural description and, consequently, an efficient algorithm.
The results show that every temporal graph can either be simplified step by step without losing any crucial information, or it contains one of five obstacles that are precisely described in mathematical terms. These obstacles explain why a single, consistent representation is not possible.
In the long term, these structural methods can help to improve the algorithmic analysis of dynamic networks — for example, when communication networks, traffic flows or data structures change over time. The TU Bergakademie Freiberg is currently developing applications of the new methods in collaboration with researchers from the Hasso Plattner Institute in Potsdam.
Research at the interface between mathematics and computer science
The presentation at the STOC conference builds on previous successes achieved by Freiberg researchers at the interface between mathematics and computer science: As early as 2023, results on the canonical decomposition of 3-connected graphs were presented at the FOCS conference, the second of the world’s two leading conferences in theoretical computer science. Taken together, these works demonstrate that TU Bergakademie Freiberg has an international profile in mathematically oriented theoretical computer science.
Original publication "Graph Minors Approach to Temporal Sequences"
