LAUSR

Leman algorithm in its plain form solves the isomorphism problem for bounded-rank width graphs. In fact, the paper even goes the crucial step further to show that canonization can be solved in the logic corresponding to the algorithm (fixed-point logic with counting). Overall, they obtain a logic that captures PTIME on graphs of bounded rank width. This means, essentially, that everything that can be algorithmically solved efficiently on these graphs can alternatively be expressed by a logical formula of fairly simple composition. Grohe had previously demonstrated this type of approach can be very fruitful. In fact, his 2017 book on the matter, spanning more than 500 pages, executes the approach for graph classes closed under taking minors. Yet, the class of graphs of bounded rank width is one of the most general classes for which the approach has been put to work successfully. Overall, in comparison to the previously best result, the paper provides us with a stronger result based on a simpler algorithm. On top of that, the overall proof is—at least from my perspective—simpler and, for many, easier to understand. Finally, the constants in the running time of the algorithm, which translate in logic terms to the number of variables needed, are small (specifically, linear in the rank width) and in some sense as small as they can be. Central to the analysis is the introduction of the novel concepts of split pairs and flip functions, which cleanly facilitate many of the arguments. It is common to find that when it comes to matters of theory, hitting the right approach, careful choice of definitions, and a hunch can make all the difference. Overall, Grohe and Neuen have found a clean and neat way to complete the logicians’ quest for graphs of bounded rank width.