一句话：为稀疏图类的一阶逻辑转导建立树状分解定理，并解决 low-shrubdepth 覆盖的开放问题。
论文研究可由一阶逻辑从稀疏图类转导得到的图类结构，重点关注有界扩张类和 nowhere dense 类。作者提出新的分解定理：此类图可表示为一个有界深度的带色有根树，并允许节点之间存在不在树中的链接，同时要求树与链接共同构成的整体保持稀疏。利用 nowhere dense 类转导的分解定理，作者进一步证明这类转导具有 low-shrubdepth 覆盖，规模与顶点数 n 和任意固定 ε > 0 相关。该结果解决了 Gajarský 等（ACM TOCL ’20）以及 Briański 等（SIDMA ’21）提出的开放问题。
We give new decomposition theorems for classes of graphs that can be transduced in first-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 , where n is the vertex count and ε > 0 is any fixed real. This solves an open problem posed by Gajarský et al. (ACM TOCL ’20) and also by Briański et al. (SIDMA ’21).
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@inproceedings{DreierGKPT22,
title = {Treelike Decompositions for Transductions of Sparse Graphs},
author = {Jan Dreier and Jakub Gajarský and Sandra Kiefer and Michał Pilipczuk and Szymon Toruńczyk},
booktitle = {LICS},
year = {2022},
doi = {10.1145/3531130.3533349}
}