2026-07-21T19:38:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18706 2024-03-06T11:02:31Z ddc:004 open_access

First Order Logic and Twin-Width in Tournaments Geniet, Colin Thomassé, Stéphan Tournaments twin-width first-order logic model checking NIP small classes We characterise the classes of tournaments with tractable first-order model checking. For every hereditary class of tournaments T, first-order model checking either is fixed parameter tractable, or is AW[*]-hard. This dichotomy coincides with the fact that T has either bounded or unbounded twin-width, and that the growth of 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: 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 FPT time for an ordered structure (T, <), this provides a FPT approximation of twin-width for tournaments. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Colin Geniet and Stéphan Thomassé 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.53 urn:nbn:de:0030-drops-187061 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.53 eng https://creativecommons.org/licenses/by/4.0/legalcode