Verteilte Graphfärbungsalgorithmen

• Antragsteller: Professor Dr. Fabian Kuhn
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 491819048

Im Bereich der verteilten Graphenalgorithmen geht es darum, zu untersuchen, wie man effizient in einem Netzwerk bestimmte Strukturen berechnen kann und welche solchen Strukturen effizient berechnet werden können. Dabei nimmt man an, dass man zum Beispiel ein Computernetzwerk gegeben hat, in welchem die Netzwerkknoten autonom agieren und miteinander über paarweise Kommunikationskanäle Informationen austauschen. In einem abstrakten, mathematischen Sinn ist ein solches Netzwerk ein Graph, die Networkknoten sind die Knoten des Graphen und die Kommunikationskanäle sind die Kanten des Graphen. Man versucht dann zu verstehen, wie oft die Knoten Informationen mit ihren direkten Nachbarn im Graphen austauschen müssen, um bestimmte Graphenprobleme zu lösen. Ein klassisches solches Graphenproblem, welches in diesem Zusammenhang seit mehr als 30 Jahren untersucht wird, ist das Graphfärbungsproblem. Dabei sollen die Knoten des Graphen so gefärbt werden, dass benachbarte Knoten verschieden gefärbt sind und so, dass gesamthaft möglichst wenige Farben verwendet werden. Graphenfärbungen in Netzwerken haben praktische Anwendungen, zum Beispiel wenn es in einem drahtlosen Netzwerk darum geht den Frequenzbereich zwischen den Knoten aufzuteilen. Das verteilte Graphenfärbungsproblem dient aber auch als wichtiger Prototyp innerhalb einer viel grösseren Klasse von sogenannten lokalen "Symmetry Breaking" Problemen. Obwohl das verteilte Graphenfärbungsproblem seit mehr als 30 Jahren intensiv untersucht wurde, gibt es immer noch viele offene Fragen. Das Ziel dieses Forschungsprojektes ist es, diese offenen Fragen anzugehen und die verteilte Komplexität des Graphenfärbungsproblems besser zu verstehen. Dabei wollen wir einerseits beweisbar schnellere verteilte Graphenfärbungsalgorithmen entwickeln und andererseits wollen wir neue untere Schranken beweisen, welche zeigen, dass eine bestimmte Laufzeit notwendig ist, um Graphen verteilt zu färben.

• DFG-Verfahren: Sachbeihilfen