论文标题
一阶逻辑和锦标赛和浓密图形的双宽度
First Order Logic and Twin-Width in Tournaments and Dense Oriented Graphs
论文作者
论文摘要
我们通过可拖动的一阶模型检查来表征锦标赛的类别。对于每个遗传类别的锦标赛$ \ Mathcal T $，一阶模型检查是固定的参数可拖动或$ \ textrm {aw} [*] $ - 硬。这种二分法与$ \ MATHCAL T $具有有限或无限的双宽度的事实相吻合，并且$ \ \ Mathcal t $的增长最多是指数级或至少是阶乘。从模型理论的角度来看，我们表明赛车的nip类与有限的双宽度相吻合。双宽度也以三个无限的障碍率家族的特征：$ \ Mathcal t $在且仅当它排除每个家庭中至少一场比赛时才限制了双宽。这是Bonnet等人的总体结果。在有序图上。这些结果的关键是一种多项式时间算法，它以$ v（t）$上的线性订单$ <$ <$ <$ <$ <$ <$ <$（t）$（t，<）的双宽度最多是$ t $ t $的双宽度的某些功能。由于可以在有序结构$（t，<）$的多项式时间内完成近似的双宽度，因此为比赛提供了双宽度的多项式时间近似。我们的结果扩展到具有稳定的有界大小的稳定集的面向图，也可以通过任意二进制关系来增强。
We characterise the classes of tournaments with tractable first-order model checking. For every hereditary class of tournaments $\mathcal T$, first-order model checking is either fixed parameter tractable or $\textrm{AW}[*]$-hard. This dichotomy coincides with the fact that $\mathcal T$ has either bounded or unbounded twin-width, and that the growth of $\mathcal T$ is either at most exponential or at least factorial. From the model-theoretic point of view, we show that NIP classes of tournaments coincide with bounded twin-width. Twin-width is also characterised by three infinite families of obstructions: $\mathcal T$ has bounded twin-width if and only if it excludes at least one tournament from each family. This generalises results of Bonnet et al. on ordered graphs. The key for these results is a polynomial time algorithm which takes as input a tournament $T$ and computes a linear order $<$ on $V(T)$ such that the twin-width of the birelation $(T,<)$ is at most some function of the twin-width of $T$. Since approximating twin-width can be done in polynomial time for an ordered structure $(T,<)$, this provides a polynomial time approximation of twin-width for tournaments. Our results extend to oriented graphs with stable sets of bounded size, which may also be augmented by arbitrary binary relations.
