First Order Logic and Twin-Width in Tournaments and Dense Oriented Graphs

Abstract

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 $\text{AW}[\ast ]$-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 that 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.

37 pages, 7 figures. Changes from v4: significant changes to sections 6 and 7