Static and Dynamic Graph Decompositions

• Applicant: Professor Dr. Harald Räcke
• Subject Area: Theoretical Computer Science
• Term: since 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 498605858

Graphs are a simple and very versatile tool for modeling relations between data. Thus, they are widely used and efficient graph algorithms are required to enable progress in many areas of computer science such as communication networks, graphics, and data mining. The goal of this proposal is to advance the understanding and development of fast graph algorithms, both for static graphs as well as for dynamically changing graphs. While the problems for static graphs that we propose are interesting by themselves, they are also chosen so as to enable the development of fast algorithms for dynamic graphs.Research in recent years has shown that a novel way of decomposing a graph, called a fast expander decomposition, can lead to faster graph algorithms for a variety of graph problems and the use of this technique for dynamic graphs has only just started. We believe that other types of (hierarchical) graph decompositions that have been used very successfully in online and approximation algorithms can also benefit from these new insights, giving the potential for large performance improvements in the static setting. In addition, these performance improvements will then also allow to use these decompositions in a dynamic setting, which will significantly enhance the toolbox for designing dynamic graph algorithms.The algorithmic problems we propose to study consist of fundamental graph algorithm questions that arise in a large variety of other research fields such as computer graphics, social network analysis, graph-based machine learning, computer networks with problems such as network routing and shortest-path finding and optimization problems in operations research.

• DFG Programme: Research Grants
• International Connection: Austria
• Partner Organisation: Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
• Cooperation Partner: Professorin Monika Henzinger, Ph.D.