Advancing Algorithmic Temporal Graph Theory

• Applicant: Dr. Hendrik Molter
• Subject Area: Theoretical Computer Science
• Term: since 2025
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 565381415

The goal of the project "Advancing Temporal Graph Theory" is to progress temporal graph algorithmics, and apply newly gained insights to problems motivated in the application areas of transportation and social networks. Temporal graphs have edge sets that may change over discrete time steps. They are a versatile model for dynamic data and hence they are naturally motivated in contexts where dynamic changes or time-dependent interactions play an important role. We plan to systematically explore temporal graph classes and structural temporal parameters (that measure similarity to certain temporal graph classes), aiming to develop new algorithmic tools for temporal graph problems. We organize specific goals into two work packages that aim to advance algorithmic temporal graph theory. Furthermore, we propose central temporal graph problems from the two mentioned application areas which we organize into four work packages. Since we expect most problems to be NP-hard, we aim to analyze the parameterized complexity of the problems and identify parameterizations that allow for so-called fixed-parameter algorithms. Current approaches to restrict input instances or find parameterizations often fail to meaningfully restrict their temporal behavior. In order to mitigate those shortcomings, we aim apply newly developed algorithmic tools.

• DFG Programme: Research Grants