Efficient reversal of transductions of sparse graph classes

Speaker(s)

Jakub Gajarský

Affiliation

University of Warsaw

Language of the talk

English

Date

Dec. 10, 2025, 2:15 p.m.

Room

room 5440

Title in Polish

Efficient reversal of transductions of sparse graph classes

Seminar

Seminar Automata Theory

---

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.

---