Twin-Width IV: Ordered Graphs and Matrices

被引:1
作者
Bonnet, Edouard [1 ]
Giocanti, Ugo [2 ]
de Mendez, Patrice Ossona [3 ,4 ]
Simon, Pierre [5 ]
Thomasse, Stephan [1 ]
Torunczyk, Szymon [6 ]
机构
[1] ENS Lyon, LIP, UMR5668, 46 Allee Italie, F-69007 Lyon, France
[2] Univ Grenoble Alpes, Lab G SCOP, CNRS, Ave Felix Viallet, F-38000 Grenoble, France
[3] CAMS CNRS UMR 8557, Paris, France
[4] Charles Univ Prague, Prague, Czech Republic
[5] Univ Calif Berkeley, Berkeley, CA USA
[6] Univ Warsaw, Krakowskie Przedmiescie 26-28, PL-00927 Warsaw, Poland
基金
欧洲研究理事会;
关键词
Twin-width; ordered graphs; matrices; finite model theory; growth jump; parameterized complexity; MONADIC 2ND-ORDER LOGIC; MINORS;
D O I
10.1145/3651151
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP classes studied in model theory, as classes that do not transduce the class of all graphs studied in finite model theory, and as classes for which model checking first-order logic is fixed-parameter tractable studied in algorithmic graph theory. This has several consequences. First, it allows us to show that every hereditary class of ordered graphs either has at most exponential growth, or has at least factorial growth. This settles a question first asked by Balogh et al. [5] on the growth of hereditary classes of ordered graphs, generalizing the Stanley-Wilf conjecture/Marcus-Tardos theorem. Second, it gives a fixed-parameter approximation algorithm for twinwidth on ordered graphs. Third, it yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures. Fourth, it provides a model-theoretic characterization of classes with bounded twin-width. Finally, it settles the small conjecture [8] in the case of ordered graphs.
引用
收藏
页数:45
相关论文
共 44 条
  • [21] Deciding first-order properties of locally tree-decomposable structures
    Frick, M
    Grohe, M
    [J]. JOURNAL OF THE ACM, 2001, 48 (06) : 1184 - 1206
  • [22] A New Perspective on FO Model Checking of Dense Graph Classes
    Gajarsky, J.
    Hlineny, P.
    Obdrzalek, J.
    Lokshtanov, D.
    Ramanujan, M. S.
    [J]. PROCEEDINGS OF THE 31ST ANNUAL ACM-IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2016), 2016, : 176 - 184
  • [23] Gajarsky J., 2018, 43 INT S MATH FDN CO
  • [24] Gajarsky J, 2018, Arxiv, DOI arXiv:1805.01823
  • [25] FO Model Checking on Posets of Bounded Width
    Gajarsky, Jakub
    Hlineny, Petr
    Lokshtanov, Daniel
    Obdrzalek, Jan
    Ordyniak, Sebastian
    Ramanujan, M. S.
    Saurabh, Saket
    [J]. 2015 IEEE 56TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2015, : 963 - 974
  • [26] Gajarsky Jakub, 2018, 45 INT C AUT LANG PR
  • [27] Ramsey-type results on singletons, co-singletons and monotone sequences in large collections of sets
    Gravier, S
    Maffray, F
    Renault, J
    Trotignon, N
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 2004, 25 (05) : 719 - 734
  • [28] Deciding First-Order Properties of Nowhere Dense Graphs
    Grohe, Martin
    Kreutzer, Stephan
    Siebertz, Sebastian
    [J]. JOURNAL OF THE ACM, 2017, 64 (03)
  • [29] Asymptotics of pattern avoidance in the Klazar set partition and permutation-tuple settings
    Gunby, Benjamin
    Palvolgyi, Domotor
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 2019, 82
  • [30] FO model checking on geometric graphs
    Hlineny, Petr
    Pokryvka, Filip
    Roy, Bodhayan
    [J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2019, 78 : 1 - 19