First Order Logic and Twin-Width in Tournaments and Dense Oriented Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918159711207424 |
|---|---|
| author | Geniet, Colin Thomassé, Stéphan |
| author_facet | Geniet, Colin Thomassé, Stéphan |
| contents | 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 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_07683 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | First Order Logic and Twin-Width in Tournaments and Dense Oriented Graphs Geniet, Colin Thomassé, Stéphan Logic in Computer Science Discrete Mathematics Combinatorics 05C20 (Primary), 05C85, 03C13, 05C30 (Secondary) G.2.2 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 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. |
| title | First Order Logic and Twin-Width in Tournaments and Dense Oriented Graphs |
| topic | Logic in Computer Science Discrete Mathematics Combinatorics 05C20 (Primary), 05C85, 03C13, 05C30 (Secondary) G.2.2 |
| url | https://arxiv.org/abs/2207.07683 |