一句话：用 lacon、shrub 与 parity 分解刻画有界扩张类的转导，并将结构有界扩张类编码到有界扩张类。
有界扩张（bounded expansion）是一类具有良好算法性质的稀疏图类，其上每个一阶逻辑可定义问题都能线性时间求解。然而，对有界扩张类做一阶解释或转导会得到更一般、可能稠密的图类，这些类看似继承稀疏类的算法性质，但缺少结构刻画。本文研究如何从有界扩张类出发刻画这类结构稀疏图。作者证明，结构有界扩张类中的图可以通过 lacon-、shrub- 与 parity-分解，由一个有界扩张类中的图编码得到；反之，这些分解给出了相应转导的刻画。该结果可用于把稀疏图类上的性质提升到结构稀疏图类，并支撑相关算法元定理。
The concept of bounded expansion provides a robust way to capture sparse graph classes with interesting algorithmic properties. Most notably, every problem definable in first-order logic can be solved in linear time on bounded expansion graph classes. First-order interpretations and transductions of sparse graph classes lead to more general, dense graph classes that seem to inherit many of the nice algorithmic properties of their sparse counterparts. In this paper, we show that one can encode graphs from a class with structurally bounded expansion via lacon-, shrub- and parity-decompositions from a class with bounded expansion. These decompositions are useful for lifting properties from sparse to structurally sparse graph classes.
@article{paperbot2213,
title = {Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes},
author = {Jan Dreier},
journal = {Logical Methods in Computer Science},
volume = {Volume 19, Issue 2},
year = {2023},
doi = {10.46298/lmcs-19(2:14)2023}
}