Efficient Reversal of Transductions of Sparse Graph Classes

(First-order) transductions are a basic notion capturing graph modifications that can be described in first-order logic. In this work, 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(n4)-time algorithm that given a graph G∈ 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 answers an open problem raised by Gajarský et al. [ACM TOCL, ’20]. In fact, for our procedure to work we only need to assume that C is monadically stable (i.e., does not transduce the class of all half-graphs) and has inherently linear neighborhood complexity (i.e., the neighborhood complexity is linear in all graph classes transducible from C). This renders the conclusion that the graph classes satisfying these two properties coincide with classes of structurally bounded expansion. Our methods also yield a O(n4)-time algorithm that computes neighborhood covers with constant overlap for monadically stable graph classes that have inherently linear neighborhood complexity.