Distributed Graph Coloring Algorithms

• Applicant: Professor Dr. Fabian Kuhn
• Subject Area: Theoretical Computer Science
• Term: since 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 491819048

In the area of ​​distributed graph algorithms, the goal is to investigate how one can efficiently compute certain structures in a network and which of these structures can be computed efficiently. One assumes that there is, for example, a computer network in which the network nodes act autonomously and exchange information with one another via pair-wise communication channels. In an abstract, mathematical sense, such a network is a graph, the network nodes are the nodes of the graph and the communication channels are the edges of the graph. One then tries to understand how often the nodes have to exchange information with their direct neighbors in the graph in order to solve certain graph problems. In this context, a classic graph problem, which has been investigated for more than 30 years, is the graph coloring problem. In this problem, the nodes of the graph have to be colored in such a way that neighboring nodes are colored differently and that overall, one uses as few colors as possible. Graph colorings in networks have practical applications, for example in order to divide the frequency domain between the nodes of a wireless network. The distributed graph coloring problem also serves as an important prototype within a much larger class of so-called local symmetry breaking problems. Although distributed graph coloring has been studied extensively for more than 30 years, there are still many open questions. The aim of this research project is to address these open questions and to better understand the distributed complexity of the graph coloring problem. On the one hand we want to develop provably faster distributed graph coloring algorithms and on the other hand we want to prove new lower bounds on the running time that is necessary to color graphs in a distributed way.

• DFG Programme: Research Grants