Zwei Informatiker fanden an einem sehr unerwarteten Ort eine Idee, die ihnen nur für einen Durchbruch in der Graphentheorie nützlich war
Im Oktober 2019 blätterten Jacob Holm und Eva Rotenberg in einem Werk, das sie einige Monate zuvor veröffentlicht hatten - und stellten plötzlich fest, dass sie auf etwas Ernstes gestoßen waren.
Seit Jahrzehnten versuchen Informatiker, einen schnellen Algorithmus zu entwickeln, um zu bestimmen, ob Kanten zu einem bestimmten Diagramm hinzugefügt werden können, damit es "planar" bleibt - das heißt, dass sich seine Kanten nicht schneiden. Es ist jedoch niemandem gelungen, den vor über 20 Jahren veröffentlichten Algorithmus zu verbessern.
Holm und Rothenberg waren überrascht, das in ihrer Arbeit zu findenEs gibt eine Idee, die es möglich gemacht hat, diesen Algorithmus ziemlich stark zu verbessern. Sie "hat eines der Haupthindernisse für einen echten Algorithmus gelöst", sagte Holm, Informatiker an der Universität von Kopenhagen. "Vielleicht haben wir dieses Problem vollständig offengelegt."
Das Paar beeilte sich, an einem neuen Artikel zu arbeiten . Sie präsentierten es im Juni auf dem Symposium der Association for Computing Machinery zur Computertheorie , wo sie eine Methode zur Überprüfung eines Diagramms auf Planarität vorstellten, die der vorherigen Version exponentiell überlegen war.
"Der neue Algorithmus ist wirklich meisterhaft", sagte Giuseppe Italiano , Informatiker an der Universität von Louis, Co-Autor eines Papiers von 1996, das jetzt den zweitschnellsten Algorithmus beschreibt. "Als ich am Schreiben dieser Arbeit teilnahm, dachte ich nicht, dass dies passieren könnte."
Diagramme sind Sammlungen von Scheitelpunkten, die durch Kanten verbunden sind. Sie können verwendet werden, um alles von sozialen Medien über Straßennetze bis hin zu elektrischen Leitern auf einer Platine zu kennzeichnen. Wenn im letzteren Fall der Graph nicht planar ist, kreuzen sich die beiden Leiter, was zu einem Kurzschluss führt.
Bereits 1913 erschienen planare Graphen in einem komplexen "kommunalen" Puzzle über drei Häuser , das im The Strand Magazine veröffentlicht wurde. In der Veröffentlichung wurden die Leser gebeten, Mitteilungen für drei Häuser zu erstellen und diese jeweils mit drei Energieträgern - Wasser, Gas und Strom - zu verbinden, damit sich die Mitteilungen nicht überschneiden. Es dauert nicht lange zu erkennen, dass diese Aufgabe unüberwindbar ist.
In Fällen mit komplexeren Graphen ist es jedoch nicht immer offensichtlich, ob sie planar sind. Es ist noch schwieriger zu sagen, ob ein komplexes Diagramm planar bleibt, wenn Sie Kanten hinzufügen - wie dies bei der Planung neuer Straßen der Fall ist.
Informatiker haben lange nach einem Algorithmus gesucht, der schnell feststellen kann, ob die gewünschte Änderung vorgenommen werden kann, damit der Graph plan bleibt, ohne jeden Teil des Graphen zu durchlaufen, wenn nur ein kleiner Teil davon geändert wird. Der Algorithmus von 1996 erforderte hierfür eine Reihe von Schritten, die ungefähr proportional zur Quadratwurzel der Anzahl der Eckpunkte im Diagramm waren.
"Es ist viel besser, als jedes Mal alles von Grund auf neu zu überprüfen, aber nicht perfekt", sagte Holm.
Der neue Algorithmus prüft die Planarität in mehreren Schritten, die proportional zum Würfel des Logarithmus der Anzahl der Eckpunkte im Diagramm sind - die Verbesserung ist exponentiell. Holm und Rothenberg von der Dänischen Technischen Universität erreichten diese Beschleunigung, indem sie eine besondere Eigenschaft planarer Graphen nutzten, die sie letztes Jahr entdeckt hatten.
Um ihre Methode zu verstehen, müssen Sie zunächst beachten, dass derselbe planare Graph auf unterschiedliche Weise gezeichnet werden kann . Alle Verbindungen dieser Optionen bleiben gleich, die Kanten können jedoch auf unterschiedliche Weise relativ zueinander angeordnet sein.
Zum Beispiel kann Abbildung A in Abbildung B geändert werden, indem das Dreieck, aus dem die Scheitelpunkte 1,2 und 3 bestehen, relativ zu der Kante, die die Scheitelpunkte 2 und 3 verbindet, invertiert wird. Die Oberseite von Abbildung B kann auch relativ zu den Scheitelpunkten 4 und 5 umgedreht werden, was zu Abbildung C führt anders, aber bezeichnen den gleichen Graphen.
Stellen Sie sich nun vor, Sie möchten eine neue Kante einfügen, die zwei Scheitelpunkte eines planaren Graphen verbindet - beispielsweise die Scheitelpunkte 1 und 6. Dazu führen Sie eine Folge von Flips aus. Von der Startposition links können Sie in zwei Umdrehungen den Scheitelpunkt 1 an die Stelle übertragen, an der er mit dem Scheitelpunkt 6 verbunden werden kann, ohne andere Kanten zu kreuzen.
In einer Arbeit von 2019 stellten Holm und Rothenberg fest, dass einige Zeichnungen mehr Vorteile für das Einfügen von Kanten haben als andere. Diese „guten“ Muster benötigen nur wenige Umdrehungen, um eine neue Kante hinzuzufügen, ohne die Planarität zu beeinträchtigen.
Was sie im Oktober verspätet erkannt haben, ist, dass ein Flip, der Sie näher an die Position bringt, an der Sie eine neue Kante hinzufügen können, das Diagramm auch näher an eines der guten Muster bringt, die sie bereits definiert haben. Indem gezeigt wird, dass eine Folge von Flips den Graphen zwangsläufig näher an die bevorzugten Muster bringt, kann ein neuer Algorithmus erstellt werden, um die Anzahl der Flips zu begrenzen, die Sie möglicherweise benötigen, um eine Möglichkeit zum Hinzufügen einer Kante zu finden (falls überhaupt möglich).
„Wir haben sehr schnell erkannt, dass mit dieser neuen Analyse das Problem gelöst werden kann
Ein Algorithmus, dessen Konzept äußerst einfach ist “, sagte Holm.
Jacob Holm und Eva Rothenberg Der
neue Algorithmus führt jeweils einen Flip durch, um eine Lösung zu finden. Infolgedessen geschieht eines von zwei Dingen: Entweder findet der Algorithmus eine Möglichkeit, die erforderliche Kante einzufügen, oder der nächste Flip bricht die vorherige ab. Danach kommt der Algorithmus zu dem Schluss, dass es keine Möglichkeit gibt, eine neue Kante hinzuzufügen.
"Wir nennen diesen Algorithmus faul-gierig", erklärte Rotenberg. "Es werden nur die Änderungen vorgenommen, die zur Aufnahme der neuen Rippe erforderlich sind."
Ihre neue Methode nähert sich der Leistung des bestmöglichen Algorithmus für solche Aufgaben an, entspricht jedoch nicht dieser. Der neue Algorithmus muss auch zu viele Schritte durchlaufen, um in den meisten realen Anwendungen verwendet zu werden - normalerweise sind Diagramme einfach genug, um Brute-Force-Tests unterzogen zu werden.
Für Holm und Rothenberg ist die Geschwindigkeit des Algorithmus jedoch nicht so wichtig wie die Ideen, die ihn beschleunigt haben. "Dieses Verständnis hat unmittelbare Auswirkungen", sagte Rotenberg.
Italiano glaubt, dass es irgendwann echte Verwendung finden wird. "Früher oder später wird es sicherlich Auswirkungen auf das haben, was außerhalb der Informatik mit Mathematik zu tun hat", sagte er.
Niemand weiß, wann noch schnellere Algorithmen erscheinen können. Dies kann einen völlig neuen Durchbruch erfordern, oder die geheime Zutat existiert möglicherweise bereits irgendwo und wartet in den Flügeln eines Stapels alter Forschung.