Jakub Gajarský: Efficient reversal of transductions of sparse graph classes

First-order transductions are graph transformations based in logic that allow us to create new graphs from old ones. They are of fundamental importance in understanding the interplay between logic and structural and algorithmic graph theory, for example in the context of the first-order model checking problem. The question whether transductions can be efficiently reversed has been open for several years. We propose an efficient algorithmic method to approximately reverse the application of a transduction, assuming the source graph is sparse. Precisely, for any graph class C that has structurally bounded expansion (i.e., can be transduced from a class of bounded expansion), we give an O(n^4)-time algorithm that given a graph G from C, computes a vertex-colored graph H such that G can be recovered from H using a first-order interpretation and H belongs to a graph class D of bounded expansion. This talk is based on a joint work with Jan Dreier and Michał Pilipczuk.