论文标题
稀疏图的转导的treelike分解
Treelike decompositions for transductions of sparse graphs
论文作者
论文摘要
我们为图形类别提供了新的分解定理，这些定理可以从稀疏图类别中转导的一阶逻辑中 - 更准确地说，是从有界扩展的类别和无处的密集类中。在这两种情况下，分解都采用了一个有界深度的单个彩色生根树的形式，此外，在树中无关的节点之间可以存在链接。约束是树由树形成的结构和链接必须稀疏。使用分解定理进行无处浓密类的转换，我们表明他们承认低左右的封面大小$ o（n^\ varepsilon）$，其中$ n $是顶点计数和$ \ varepsilon> $ \ varepsilon> 0 $是任何固定的〜ery〜ere。这解决了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 from 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(n^\varepsilon)$, where $n$ is the vertex count and $\varepsilon>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).
