Efficient Temporal-Graph Algorithms

• Applicant: Professor Dr. Frank Kammer
• Subject Area: Theoretical Computer Science
• Term: since 2026
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 571642628

The objective of this project is to develop efficient algorithms for temporal graphs. We define efficiency in three ways: (1) Primarily optimizing the runtime of an algorithm without sacrificing solution quality. (2) Space-efficient algorithms that maintain the asymptotic runtime and solution quality of standard algorithms while reducing the space requirement. (3) Sublinear-time algorithms that solve problems approximately via randomization while considering only a small fraction of the input. Our main focus for (1) are temporal graph traversal problems such as temporal exploration that asks for a temporal walk visiting all vertices of a given temporal graph. Such a walk is commonly called an exploration schedule. First, we aim to improve upon the known upper- and lower bounds on the number of time steps required for exploration schedules in some temporal graphs. Second, we aim to design heuristics for computing exploration schedules. Other traversal problems we are interested in are so-called agent-based problems. For example, we study temporal rendezvous, which requires two agents to meet in a temporal graph. We are interested in restricting the computational power of the agents to allow only polynomial time, which improves current state-of-the-art temporal rendezvous strategies that require super-polynomial computation time. For (2), we focus on space-efficient variants of basic temporal graph algorithms such as computing temporal walks that meet certain optimality criteria. Similar to depth-first and breadth-first searches in static graphs, these algorithms often form the basis for solving more complex temporal-graph problems. Although linear-time algorithms exist, they are not space-efficient. Additionally, we are interested in expanding the work on space-efficient data structures for temporal graphs and their representations (compact or succinct). Prior work on succinct temporal graphs had little focus on the input distribution, while for static graphs restricting the input to certain graphs is common and gives better bounds. For example, much research has been done on succinct encodings of planar or interval graphs. Our goal is to design succinct encodings for restricted temporal graph classes. Additionally, we are interested in space-efficient algorithms for iso- and automorphisms of certain (temporal) graph classes, as these have applications to the previously mentioned agent-based problems. For (3), we consider sublinear-time algorithms that approximate certain properties of temporal graphs. As there are currently no sublinear-time algorithms for temporal graphs, we are interested in presenting first results for basic properties such as approximating the average temporal degree of a vertex, which is the number of time edges incident to a vertex throughout the lifetime of the temporal graph. Other examples include approximating the number of temporally connected components and the earliest arrival time of temporal walks.

• DFG Programme: Research Grants