Dreier, J., Gajarský, J., Kiefer, S., Pilipczuk, M., & Toruńczyk, S. (2022). Treelike Decompositions for Transductions of Sparse Graphs. In Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science (pp. 1–14). Association for Computing Machinery, Inc. https://doi.org/10.1145/3531130.3533349
We give new decomposition theorems for classes of graphs that can be transduced in frst-order logic from classes of sparse graphs - more precisely, from classes of bounded expansion and nowhere dense classes. In both cases, the decomposition takes the form of a single colored rooted tree of bounded depth where, in addition, there can be links between nodes that are not related in the tree. The constraint is that the structure formed by the tree and the links has to be sparse. Using the decomposition theorem for transductions of nowhere dense classes, we show that they admit low-shrubdepth covers of size O(ne), where n is the vertex count and e > 0 is any fxed real. This solves an open problem posed by Gajarský et al. (ACM TOCL '20) and also by Brianski et al. (SIDMA '21).
