Twin-Width IV: Ordered Graphs and Matrices*

被引:27
作者
Bonnet, Edouard [1 ]
Giocanti, Ugo [1 ]
de Mendez, Patrice Ossona [2 ]
Simon, Pierre [3 ]
Thomasse, Stephan [1 ]
Torunczyk, Szymon [4 ]
机构
[1] ENS Lyon, Lip UMR5668, Lyon, France
[2] CAMS CNRS UMR 8557, Lyon, France
[3] Univ Calif Berkeley, Berkeley, CA USA
[4] Univ Warsaw, Warsaw, Poland
来源
PROCEEDINGS OF THE 54TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '22) | 2022年
基金
欧洲研究理事会;
关键词
Twin-width; matrices; ordered graphs; enumerative combinatorics; model theory; algorithms; computational complexity; Ramsey theory; MONADIC 2ND-ORDER LOGIC; HEREDITARY PROPERTIES; MINORS;
D O I
10.1145/3519935.3520037
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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, Bollobas, and Morris [Eur. J. Comb. '06] 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 twin-width 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 our small conjecture [SODA '21] in the case of ordered graphs.
引用
收藏
页码:924 / 937
页数:14
相关论文
共 50 条
[41]   How to compute digraph width measures on directed co-graphs [J].
Gurski, Frank ;
Komander, Dominique ;
Rehs, Carolin .
THEORETICAL COMPUTER SCIENCE, 2021, 855 :161-185
[42]   Structural Recursion for Querying Ordered Graphs [J].
Hidaka, Soichiro ;
Asada, Kazuyuki ;
Hu, Zhenjiang ;
Kato, Hiroyuki ;
Nakano, Keisuke .
ACM SIGPLAN NOTICES, 2013, 48 (09) :305-318
[43]   Rounding in symmetric matrices and undirected graphs [J].
Hell, P ;
Kirkpatrick, D ;
Li, B .
DISCRETE APPLIED MATHEMATICS, 1996, 70 (01) :1-21
[44]   Noncommuting graphs of matrices over semirings [J].
Dolzan, David ;
Oblak, Polona .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2011, 435 (07) :1649-1656
[45]   Drug delivery from ordered mesoporous matrices [J].
Manzano, Miguel ;
Colilla, Montserrat ;
Vallet-Regi, Maria .
EXPERT OPINION ON DRUG DELIVERY, 2009, 6 (12) :1383-1400
[46]   Extremal theory of vertex or edge ordered graphs [J].
Tardos, Gabor .
SURVEYS IN COMBINATORICS 2019, 2019, 456 :221-236
[47]   A New Width Parameter of Graphs Based on Edge Cuts: α-Edge-Crossing Width [J].
Chang, Yeonsu ;
Kwon, O-Joung ;
Lee, Myounghwan .
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2023, 2023, 14093 :172-186
[48]   Relational Width of First-Order Expansions of Homogeneous Graphs with Bounded Strict Width [J].
Wrona, Michal .
37TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2020), 2020, 154
[49]   ON THE STRUCTURE OF GRAPHS WITH PATH-WIDTH AT MOST TWO [J].
Barat, Janos ;
Hajnal, Peter ;
Lin, Yixun ;
Yang, Aifeng .
STUDIA SCIENTIARUM MATHEMATICARUM HUNGARICA, 2012, 49 (02) :211-222
[50]   Flip-width: Cops and Robber on dense graphs [J].
Torunczyk, Szymon .
2023 IEEE 64TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, FOCS, 2023, :663-700