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

07/15/2022
by   Colin Geniet, et al.
0

We characterise the classes of tournaments with tractable first-order model checking. For every hereditary class of tournaments 𝒯, first-order model checking either is fixed parameter tractable, or is AW[*]-hard. This dichotomy coincides with the fact that 𝒯 has either bounded or unbounded twin-width, and that the growth of 𝒯 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: 𝒯 has bounded twin-width if and only if it excludes 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 compute 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 polytime 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset