Problems of unknown complexity : graph isomorphism and Ramsey theoretic numbers

Abstract

We consider three computational problems with unknown complexity status: The graph isomorphism problem, the problem of computing van der Waerden numbers and the problem of computing Ramsey numbers. For each of the problems, we devise an algorithm that we analyze with theoretical and practical means by a comparison with contemporary algorithms that solve the respective problems. The ScrewBox algorithm solves the graph isomorphism problem by a random sampling process. Given two graphs, the algorithm randomly searches an invariant that may be randomly evaluated quickly and that shows significant statistical difference on the input graphs. This invariant is gradually and adaptively constructed depending on the difficulty of the input. Isomorphism is certified by supplying an isomorphism. Non-isomorphism is certified by the ScrewBox, the invariant whose statistical behavior deviates on the input graphs, together with the appropriate statistical test. The wildcards algorithm for van der Waerden numbers solves the second problem. Its key technique is to treat colorings of integers avoiding monochromatic arithmetic progressions simultaneously by allowing ambiguity. This, together with a specific preprocessing step, forms the algorithm that is used to compute previously unknown van der Waerden numbers. The wildcards algorithm for Ramsey numbers combines the techniques and algorithms with which we approach the first two problems to solve the third problem.

Wir entwickeln Algorithmen für drei kombinatorische Probleme unbekannter Komplexität: Das Graphisomorphieproblem, die Berechnung von van der Waerden-Zahlen und die Berechnung von Ramsey-Zahlen. Mit theoretischen und praktischen Methoden wird ein Vergleich zu bereits existierenden Algorithmen gezogen. Der Schraubenkasten, ein zertifizierender, randomisierter Graph-nicht-Isomorphie Algorithmus, führt zufällige Stichproben in zwei gegeben Graphen durch, und schließt durch Festellen von statistisch signifikant abweichendem Verhalten der gesammelten Daten auf Nichtisomorphie. Die Durchführung der Stichproben und damit die erhaltenen Daten sowie die verwendete Methode zum Festellen statistisch abweichenden Verhaltens passen sich dabei den Eingabegraphen an. Auf isomorphen Graphen wird mit hoher Wahrscheinlichkeit ein Isomorphismus gefunden, der als Zertifikat dient. Für nichtisomorphe Eingabegraphen dienen als randomisiertes Zertifikat die Zusammensetzung des Schraubenkastens und die Spezifizierung eines günstigen statistischen Tests. Zur Berechnung von van der Waerden-Zahlen entwickeln wir einen Algorithmus, der durch die Verwendung von Platzhaltern ein gleichzeitiges Bearbeiten von verschiedenen Elementen des zu durchsuchenden Lösungsraums ermöglicht. Mit ihm werden neue van der Waerden- Zahlen berechnet. Der Zusammenhang der ersten beiden Probleme ist durch das dritte gegeben, dessen Lösung die anderen Lösungen zu einem Algorithmus verknüpft, der Ramsey-Zahlen berechnet.