Efficient reversal of transductions of sparse graph classes

Prelegent(ci)

Jakub Gajarský

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

10 grudnia 2025 14:15

Pokój

p. 5440

Tytuł w języku polskim

Efficient reversal of transductions of sparse graph classes

Seminarium

Seminarium „Teoria automatów”

---

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.

---