Seit über 25 Jahren galt ein theoretisches Limit in der Informatik, das die Berechnung kürzester Pfade in großen Netzwerken behinderte. Ein neues Forschungsresultat des Indian Institute of Technology Gandhinagar schließt nun diese Lücke. Dr. Manoj Gupta, Associate Professor an der IIT Gandhinagar, stellte auf dem 66. Symposium zur Grundlagen der Informatik (FOCS 2025) einen deutlich verbesserten Algorithmus vor, der das Problem der kürzesten Pfade zwischen allen Knotenpaaren effizienter löst. Das zugrundeliegende Problem, bekannt als "All-Pairs Shortest Paths" (APSP), fragt nach dem kürzesten Weg zwischen jedem möglichen Punktepaar in einem Netzwerk. Solche Graphen können Transportnetze, Kommunikationsinfrastrukturen oder biologische Systeme wie Proteinkontakte abbilden. Die exakte Berechnung dieser Distanzen in dichten Netzen ist extrem zeitintensiv. Verdoppelt sich die Netzwerkgröße, vervier- oder verzehnfacht sich der Rechenaufwand erheblich. Daher konzentriert sich die Forschung seit Jahrzehnten auf Approximationsalgorithmen, die Ergebnisse liefern, die dem wahren Wert nahekommen, aber in deutlich kürzerer Zeit berechnet werden können. Bereits im Jahr 1996 bewiesen die Forscher Dor, Halperin und Zwick (DHZ), dass man Distanzen mit einer Fehlermarge von maximal dem Zweifachen des wahren Wertes (sogenannte 2-Approximation) in fast optimaler Zeit berechnen kann. Ihr Ansatz stützte sich auf das Stichprobenverfahren. Dabei wurden zufällig ausgewählte Knoten des Netzwerks analysiert, um Schätzungen für weite Distanzen zu liefern. Für große Entfernungen, etwa zwischen zwei weit voneinander entfernten Städten, erwies sich diese Methode als zuverlässig, da es wahrscheinlich war, dass ein Stichprobenknoten auf dem optimalen Pfad lag. Das Problem trat jedoch bei kurzen Distanzen auf. Bei nahen Knotenpaaren, wie zwei Stadtteilen in derselben Metropole, war die Garantie, dass die Schätzung nicht mehr als das Doppelte des wahren Wertes beträgt, oft gebrochen. Ein tatsächlicher Pfad von zwei Schritten konnte fälschlicherweise als fünf Schritte geschätzt werden. Diese Einschränkung bestand nun fast ein Vierteljahrhundert lang unangetastet. Dr. Gupta hat diesen Zustand durch eine mehrstufige Verfeinerung des Stichprobenverfahrens gebrochen. Im Gegensatz zu früheren Ansätzen, die auf einer einzigen Ebene von Stichprobenknoten basierten, nutzt der neue Algorithmus mehrere Skalenebenen. Dabei wird die Struktur des Graphen auf unterschiedlichen Ebenen geschichtet, sodass auch kürzeste Pfade zuverlässig erfasst werden können. Der entscheidende Vorteil liegt darin, dass die Gesamtgeschwindigkeit des Algorithmus erhalten bleibt, während die Mindestentfernung, für die die 2-Approximationsgarantie gilt, deutlich sinkt. Dieser theoretische Fortschritt ist von großer praktischer Bedeutung. Die effiziente Berechnung von Näherungswerten ist essenziell für die Skalierung moderner Systeme, von Internet-Routing und Verkehrsnetzen bis hin zu sozialen Plattformen und KI-Modellen. Oft ist eine präzise exakte Berechnung nicht notwendig, sondern vielmehr Geschwindigkeit und Zuverlässigkeit bei großen Datenmengen. Durch das Senken der theoretischen Untergrenze für diese Garantie, die seit 1996 bestand, stärkt Dr. Gupatas die Fundamente skalierbarer Graphenalgorithmen. Dieser Erfolg zeigt, wie globale Strukturen aus lokalen Verbindungen entstehen können und ebnet den Weg für schnellere und leistungsfähigere vernetzte Systeme in der Zukunft.