Anders, Markus (2024)
Efficient Algorithms for Symmetry Detection.
Technische Universität Darmstadt
doi: 10.26083/tuprints-00028257
Dissertation, Erstveröffentlichung, Verlagsversion

Kurzbeschreibung (Abstract)

The use of symmetry dramatically impacts the efficiency of algorithms in various application areas. However, no matter how symmetries are used, there needs to be a way to obtain them efficiently. In practice, symmetries of combinatorial structures are usually computed by modeling said structure as a graph. The automorphisms of this graph then precisely model the symmetries of the combinatorial structure. A so-called practical graph isomorphism solver is then used to compute the automorphism group of the constructed graph. Practical graph isomorphism solvers have been developed for more than half a century. While all state-of-the-art solvers are based on the same principles, namely the so-called individualization-refinement paradigm, there are vast differences among them. The differences in the algorithms, in turn, lead to vast performance differences in practice. While practical graph isomorphism has been considered "solved" multiple times over the past few decades, no single algorithm can efficiently solve all the graphs stemming from the various application areas. Indeed, there are even some particular applications for which state-of-the-art implementations struggle to solve all the graphs efficiently. Ideally, one would like to have a singular algorithm that is fast on all graphs.

In this thesis, we describe the design of a new practical graph isomorphism solver called dejavu. Instead of trying to develop a better implementation ad hoc, we perform a theoretical analysis of essential algorithmic ingredients used in state-of-the-art algorithms. A central result is a theoretical model for the backtracking behavior of all state-of-the-art algorithms. Within this model, we prove that a Monte Carlo strategy is optimal in the worst-case up to logarithmic factors. A Monte Carlo strategy can use randomization and is allowed to err with bounded probability. In particular, we prove that randomized strategies outperform deterministic strategies. In theory, the Monte Carlo backtracking strategy outperforms all strategies currently used in practice in the worst-case. Further theoretical results include a characterization of the structure of the aforementioned backtracking trees and an analysis of design choices in the so-called color refinement algorithm, a crucial subroutine used by the solvers.

In turn, the design of dejavu is based on these theoretical results. In particular, the backtracking strategy of dejavu follows the near-optimal Monte Carlo strategy. The solver further contains various novel practical components. These components are carefully designed to complement the Monte Carlo strategy. Notably, one of the components is a preprocessor designed to shrink large and sparse inputs, which can also be used with all the other state-of-the-art solvers. Benchmarks on a vast library of graphs reveal that dejavu is faster than any other state-of-the-art solver on most tested graph classes.

Frage zum Eintrag

Redaktionelle Details anzeigen