Twin-width I: tractable FO model checking

Édouard Bonnet; Eun Jung Kim; Stéphan Thomassé; Rémi Watrigant

Source-linked AI summary

Twin-width I: tractable FO model checking

Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant

arXiv:2004.14789v3Apr 30, 2020cs.DScs.DMcs.LO

TL;DR

The paper asks whether Guillemot and Marx’s permutation width parameter has a useful graph-theoretic generalization and develops twin-width for graphs, matrices, and binary structures. It establishes bounded twin-width for many classes and shows that, given a contraction witness, FO model checking runs in linear FPT time in the structure size. The framework also preserves bounded twin-width under FO interpretations and transductions, while its dependence on formula size is non-elementary and computing witnesses generally remains unresolved.

Problem
The paper addresses whether a permutation width parameter can be generalized to graphs and matrices in a way useful for algorithms and structural complexity.
Method
The paper defines twin-width through iterative near-twin contractions tracked by bounded-degree red edges, and uses contraction sequences, matrix orderings, and combinatorial FO evaluation trees.
Results
FO model checking is FPT on bounded-twin-width classes given a d-contraction sequence, with runtime f(|φ|, d) · n for a computable non-elementary function f.
Takeaways & Limitations
Bounded twin-width unifies and extends FPT FO model checking across non-monotone classes, including binary structures and classes such as bounded rank-width graphs, grids, and geometric graphs.
Takeaways & Limitations
The FO algorithm requires a supplied contraction sequence, and the dependence on formula size is non-elementary; computing twin-width sequences on general graphs remains an open problem.

Abstract

from arXiv · show

Inspired by a width invariant defined on permutations by Guillemot and Marx [SODA '14], we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes, bounded rank-width graphs, map graphs, $K_t$-free unit $d$-dimensional ball graphs, posets with antichains of bounded size, and proper subclasses of dimension-2 posets all have bounded twin-width. On all these classes (except map graphs without geometric embedding) we show how to compute in polynomial time a sequence of $d$-contractions, witness that the twin-width is at most $d$. We show that FO model checking, that is deciding if a given first-order formula $φ$ evaluates to true for a given binary structure $G$ on a domain $D$, is FPT in $|φ|$ on classes of bounded twin-width, provided the witness is given. More precisely, being given a $d$-contraction sequence for $G$, our algorithm runs in time $f(d,|φ|) \cdot |D|$ where $f$ is a computable but non-elementary function. We also prove that bounded twin-width is preserved by FO interpretations and transductions (allowing operations such as squaring or complementing a graph). This unifies and significantly extends the knowledge on fixed-parameter tractability of FO model checking on non-monotone classes, such as the FPT algorithm on bounded-width posets by Gajarský et al. [FOCS '15].

1 Introduction

The paper introduces twin-width as a graph and matrix width parameter generalizing a permutation invariant, and develops it as a unifying framework for structural complexity and FO model checking. Bounded twin-width includes many graph and relational classes, supports efficiently computed contraction witnesses in several cases, and yields linear-time FPT FO model checking when a witness is given.

Motivation and scope: Twin-width generalizes a permutation width parameter to graphs and matrices, connecting computational complexity, model theory, enumeration, and decomposition methods.The paper positions bounded twin-width as a natural class for which FO model checking is linear and which is stable under first-order interpretations.
Definition and intuition: Bounded twin-width contracts a graph iteratively by merging near-twins while keeping the red-edge degree bounded.Red edges record uncertainty created by contractions; a d-trigraph has red-edge maximum degree at most d.
Classes and constructions: The framework covers proper minor-closed classes, bounded rank-width graphs, grids, and geometric classes including unit d-dimensional ball graphs with bounded clique number.For unit d-dimensional ball graphs with clique number k, the paper gives contraction sequences with a bound involving ⌈d/2⌉ and k when the geometric representation is available.
Computing witnesses: The paper gives a matrix-based route to contraction sequences by finding vertex orderings whose adjacency matrices have controlled block structure, using Marcus–Tardos arguments on corners.This ordering framework is designed for classes such as planar graphs, where directly finding a contraction sequence is challenging.
Scope and open problems: Bounded twin-width has broad but non-universal scope: cubic graphs and several random or high-girth graph families have unbounded twin-width, while some bounded-degree grids do not.The paper also notes that computing twin-width or contraction sequences efficiently on general graphs remains an open problem.
FO model checking: Given a d-contraction sequence, FO model checking on an n-vertex graph or digraph runs in time f(|φ|, d) · n for a computable non-elementary function f.The result extends to binary structures and supplies a linear-time FPT algorithm in the formula size when the contraction witness is provided.

2 Preliminaries

This section fixes graph, matrix, first-order logic, model-checking, and interpretation/transduction terminology used throughout the paper.

Graph definitions and notations: Graphs are undirected and simple, with V(G) and E(G) denoting vertices and edges, while neighborhoods and adjacency matrices provide standard representations.The paper distinguishes open and closed neighborhoods and defines adjacency matrices relative to a vertex ordering.
Graph definitions and notations: A contraction merges two vertices without requiring adjacency, whereas a classical edge contraction requires adjacent vertices; graph minors additionally allow vertex and edge deletions.The paper explicitly overloads “contraction” for non-adjacent vertex identification.
First-order logic: A finite relational structure interprets relation symbols over a finite domain, and a binary structure uses only relations of arity two.A sentence is true in a structure when it evaluates to true under the usual quantified Boolean semantics.
Model checking: FO model checking asks whether a finite structure M satisfies a sentence φ, with brute force taking time |M|^|φ|.The paper seeks algorithms parameterized by |φ|, ideally running in time f(|φ|)|D|.
FO interpretations and transductions: FO interpretations define output relations by fixed formulas, while transductions extend this with domain filtering, unary expansions, and copied structures.Interpretations can produce graph complements or squares, and transductions combine expansion, copying, and a basic FO transduction.
FO interpretations and transductions: Bounded twin-width is preserved under FO interpretations and transductions, providing robustness for first-order model checking.The paper states this preservation as a worthwhile property of bounded-twin-width classes.

3 Sequence of contractions and twin-width

Twin-width controls cumulative neighborhood errors during repeated contractions by recording them as red edges and bounding their degree.

Motivation and intuition: Near-twin contractions generalize cograph contractions by merging vertices whose neighborhoods differ on only a bounded number of elements.The motivation is to extend tractability beyond cographs while controlling accumulated errors.
Trigraphs and red edges: A trigraph separates ordinary edges from red edges, with red edges marking uncertainty caused by contraction errors.A d-trigraph has red-edge maximum degree at most d.
Contraction rule: Contracting u and v makes wx black only when both ux and vx are black edges, leaves wx absent when both are absent or red, and marks it red otherwise.Existing red edges remain red through contraction.
Twin-width: A graph is d-collapsible when a sequence of d-contractions reduces it to one vertex, and its minimum such d is twin-width.The sequence consists of trigraphs with successively fewer vertices.
Examples: Cographs have twin-width 0, paths of length at least three have twin-width 1, and trees have twin-width 2.The paper also states that red paths have twin-width at most 2.
Extensions: The framework extends to directed graphs and partial orders by creating red edges when contracted vertices relate differently to another vertex.Matrices later provide a unifying framework for structures colored by a constant number of unary relations.

4 First properties and examples of classes with bounded twin-width

Twin-width is preserved under complementation and induced subgraphs, while adding an apex increases it by at most a factor expressed by Theorem 2. The section also gives bounded-twin-width results for grids, ball graphs, and boolean-width graphs, while identifying important limitations.

Complementation and induced subgraphs: Twin-width is invariant under complementation, so every d-contraction sequence remains valid after complementing the graph.
Complementation and induced subgraphs: The twin-width of an induced subgraph is at most the twin-width of the original trigraph.A contraction sequence can be projected by ignoring contractions involving vertices outside the induced subgraph.
Limitations: Twin-width does not capture bounded mim-width graphs, and bounded twin-width is not preserved under non-induced subgraphs and minors.Interval graphs have mim-width 1, while line graphs of bicliques witness unbounded twin-width for the class of all graphs.
Grids: 3d bounds the twin-width of every d-dimensional n-grid, and the bound also applies to every subgraph of such a grid.The paper notes that twin-width remains constant on fixed-dimensional grids even where other width parameters are unbounded.
Geometric graph classes: (3⌈d⌉)^dk bounds the twin-width of subgraphs of unit d-dimensional ball graphs with clique number k, with polynomial-time sequences when coordinates are given.

5 The grid theorem for twin-width

The matrix formulation replaces graph edges with entries over a finite alphabet and uses a special red value to record errors created during contractions.

Matrices use entries from a finite alphabet containing a special value r representing errors during computations.
The red matrix value plays the same role as red edges in the graph formulation.
The matrix framework extends twin-width beyond graphs by treating contraction errors as red entries.

5.1 Twin-width of matrices, digraphs, and binary structures

Twin-width extends from graphs to matrices, digraphs, and binary structures through adjacency-matrix encodings, with unary relations enforced as contraction constraints.

Matrices: A matrix contraction merges two columns or rows and replaces disagreements by the red value r.The matrix twin-width bounds the maximum number of red entries in any row or column throughout a contraction sequence.
Digraphs and binary structures: Digraph twin-width is defined as symmetric twin-width of an adjacency matrix encoding one-way, two-way, and absent arcs with values -1, 1, 2, and 0.
Digraphs and binary structures: Binary structures encode each ordered pair by a tuple of relation values, and their twin-width is the symmetric twin-width of the resulting matrix.
Unary relations: Contractions in structures augmented by h unary relations are allowed only between vertices sharing exactly the same unary relations.Such sequences may stop with at most 2h vertices, and the twin-width is at most 2h · tww(G).

5.2 Partition coarsening, contraction sequence, and error value

The partition view represents contractions as successive coarsenings and measures errors through nonconstant zones, yielding a convenient upper-bound lemma for twin-width.

Partition contractions: A matrix partition consists of a row-partition and a column-partition, and a contraction merges two parts in either partition.
Partition contractions: A contraction sequence runs from the finest singleton partition to the coarsest one-part partition through successive contractions.
Error values: The error value of a row or column counts the nonconstant zones incident with that part.A zone is constant when all entries in its row-part and column-part intersection are identical.
Error values: Twin-width is the minimum t for which a contraction sequence has error value at most t throughout.
Coarsening lemma: rt bounds twin-width when every partition in a coarsening sequence has error value at most t and each coarsening part contains at most r finer parts.The factor r arises by expanding each nonconstant coarser zone into at most r finer zones.

5.3 Matrix division and the Marcus-Tardos theorem

Matrix divisions partition rows and columns into consecutive parts, enabling contractions that preserve this structure. The Marcus–Tardos theorem links sufficient linear density of 1-entries to the existence of grid minors.

Matrix divisions: A division pairs a row-division with a column-division, and a fusion contracts two consecutive parts of either partition.Division sequences restrict contractions to operations preserving consecutive row and column blocks.
Grid minors: A t-grid minor is a (t,t)-division in which every zone contains at least one 1.Grid minors certify structured complexity in 0,1-matrices.
Marcus–Tardos theorem: The Marcus–Tardos theorem states that every n × m 0,1-matrix with at least c_t max(n,m) ones contains a t-grid minor.The constant c_t depends only on t.
Motivation: The theorem is most informative for sparse matrices because dense matrices necessarily contain many 1-entries and therefore large grid minors.The paper seeks a complexity notion extending this perspective to dense matrices as well.

5.4 Mixed minor and the grid theorem for twin-width

Mixed minors extend grid-minor complexity by requiring every zone to vary locally rather than merely contain a 1. The grid theorem for twin-width connects mixed-minor exclusion with bounded twin-width after suitable row and column ordering.

Mixed minors: A matrix is mixed when it is neither vertical nor horizontal, and a t-mixed minor is a division whose every zone is mixed.Vertical means adjacent rows agree entrywise, while horizontal means adjacent columns agree entrywise.
Mixed minors: The all-1 matrix is 1-mixed free but admits an n-grid minor, showing that grid minors and mixed minors detect different structure.This distinction motivates using mixed minors for dense matrices.
Grid theorem: T-mixed free matrices are exactly matrices with bounded twin-width, up to reordering rows and columns.This is the section’s principal structural equivalence.
Grid theorem: Every t-twin-ordered matrix is 2t + 2-mixed free, while every t-mixed free matrix has twin-width at most 4c_tα^(4c_t+2) = 2^(2^O(t)).The alphabet size is denoted by α, and the bound is also written as 2^(2^O(t)) in the supplied result.
Algorithmic use: To bound a graph’s twin-width, it suffices to find a vertex ordering whose adjacency matrix has no t-mixed minor.The paper presents this as a simplification of directly constructing a contraction sequence.
Sanity check: Random 0,1-matrices have large grid minors under every row and column reordering, and random bipartite graphs consequently have unbounded twin-width.This provides a sanity check for the grid theorem.

5.5 Corners

Corners are local 2-by-2 witnesses of matrix mixedness. This equivalence supplies the key local object used in the proof of the grid theorem.

Corner definition: A corner is a consecutive 2-by-2 submatrix that is mixed.Corners localize variation within a matrix.
Corner characterization: A matrix is mixed if and only if it contains a corner.The forward direction follows by propagating the absence of corners to force horizontal or vertical structure.
Role in the proof: Figure 5 marks mixed zones and mixed cuts with corners, illustrating how local witnesses track mixed value during contractions.The figure also shows that zone counts can change while the total mixed value remains controlled.

5.6 Mixed zones, cuts, and values

Mixed value combines mixed zones and mixed cuts to measure variation across a division. This quantity does not increase when consecutive row or column parts are fused.

Definitions: A mixed zone is a zone that is mixed, while a mixed cut is a boundary between consecutive row parts whose two boundary rows form a mixed matrix.These definitions apply relative to a consecutive column set and a row-division.
Mixed value: The mixed value is the sum of the numbers of mixed cuts and mixed zones.Counting both prevents contractions from hiding variation when mixed zones merge or change.
Monotonicity: Contracting two consecutive row parts does not increase the mixed value measured on a column set.Any newly mixed fused zone must contain a prior mixed zone or mixed cut.
Division measure: The mixed value of a division is the maximum value over all row parts on the column division and all column parts on the row division.The finest division has mixed value 0, while the coarsest division has mixed value at most 1.

5.7 Finding a division sequence with bounded mixed value

The paper constructs a division sequence with uniformly bounded mixed value for every t-mixed-free matrix, using greedy fusions and the Marcus–Tardos theorem.

Every t-mixed-free matrix has a division sequence in which each division has mixed value at most 2c_t.
The sequence is built by starting from the finest division and greedily fusing parts while preserving the mixed-value bound.
If no row fusion is possible, each candidate fused row-part contains more than 2c_t corners in mixed zones and cuts.
Two offset column refinements convert these corners into enough mixed zones to invoke the Marcus–Tardos theorem.

5.8 Finding a contraction sequence with bounded error value

The bounded-mixed-value division sequence is refined into bounded-error partitions, which then yield a contraction sequence with an explicit twin-width bound and a constructive algorithm.

The division sequence with small mixed value serves as a frame for constructing a contraction sequence with bounded error value.
For a t-mixed-free matrix over an alphabet of size α, the construction sets t′ = 2c_t and refines each division into row and column types.
The refined partition has error value at most t′α^(t′+1), because nonconstant zones can only arise over at most t′ mixed column-parts.
The refinement remains controlled across successive divisions, with each partition 2α^(t′+1)-refining the next.
The resulting twin-width bound is 4c_tα^(4c_t+2), obtained by applying Lemma 8 to the refined sequence.
A k-mixed-free ordering of an n × n matrix yields a 2^(2O(k))-sequence computable in O(n^2) time.
For mixed-symmetric matrices, the construction can be made symmetric, producing a symmetric contraction sequence with error value 2^(2O(k)).

6 Classes with bounded twin-width

The framework applies twin-width to permutations, posets, and minor-closed graphs, establishing boundedness through mixed-free matrices and explicit structural arguments.

6.1 Pattern-avoiding permutations: Twin-width generalizes the Guillemot–Marx permutation parameter from permutations to graphs and matrices.
6.1 Pattern-avoiding permutations: For pattern-avoiding permutations, the associated ordered digraph transforms the permutation matrix into a 2k-mixed-free adjacency matrix, enabling FO model checking.
6.1 Pattern-avoiding permutations: An algorithm solves the stated artificial permutation problem in f(ℓ, |σ|, |σ′|) · |τ| time after distinguishing a mixed minor from bounded twin-width.
6.1 Pattern-avoiding permutations: FO model checking is FPT on every hereditary proper subclass of permutation graphs and every proper subclass of dimension-2 partial orders.
6.2 Posets of bounded width: Posets of width k have twin-width at most 4c_k · 4^(4c_k+2) = 2^(2O(k)), using a chain ordering and transitivity to exclude a mixed minor.
6.3 Proper minor-closed classes: Every K_t-minor-free graph has twin-width at most f(t) = 2^(2^(2O(t))), proved by showing its ordered adjacency matrix is g(t)-mixed-free.
6.3 Proper minor-closed classes: For planar graphs, the resulting constant bound has billions of digits, and planar d-trigraphs need not admit a planarity-preserving d-contraction.

7 FO model checking

The paper makes FO model checking fixed-parameter tractable on graphs with bounded twin-width when a contraction witness is provided, using bounded reductions of morphism-trees computed along the partition sequence.

FO model checking: Given a prenex formula of length ℓ, an n-vertex graph, and a d-sequence, model checking runs in time f(ℓ, d) · n.The dependence on formula length may be non-elementary.
Morphism-tree reductions: Every reduct of an ℓ-morphism-tree has size bounded by a function h(ℓ), because each node has only boundedly many non-equivalent extensions.At depth ℓ−1, the number of non-equivalent children is at most 2^(ℓ−1) + ℓ−1.
FO model checking: A minimax computation on a reduced ℓ-morphism-tree decides whether the graph satisfies the prenex formula.Existential quantifiers induce maxima, universal quantifiers induce minima, and reductions preserve the computed root value.
Dynamic programming: Using a sequence of d-partitions, the paper computes the required reduced morphism-tree in time f(ℓ, d) · n.The computation proceeds iteratively from the finest partition to the coarsest one.
Dynamic programming: Pruned shuffles combine local reduced morphism-trees into a reduction of the global morphism-tree, while preserving the structures needed for model checking.The shuffle construction is exact for complete morphism-trees and remains a reduction when applied to local reducts.
Consequences: The same framework yields linear-parameter algorithms for several problems, including k-Independent Set, k-Clique, and k-Subgraph Isomorphism.These bounds require the d-sequence to be given.

8 Stability under FO interpretations and transductions

The paper proves that bounded twin-width is preserved under first-order interpretations and transductions, including operations such as graph squaring and complementing. This stability yields bounded twin-width for further graph classes, including map graphs derived from planar graphs.

FO interpretations: Bounded twin-width is invariant under first-order interpretations, addressing constructions such as graph squaring whose effect on twin-width is otherwise unclear.A graph interpretation adds an edge according to a first-order formula evaluated on the original graph.
FO transductions: Any (φ, γ, h)-transduction of a graph of twin-width at most d has twin-width bounded as a function of |φ|, γ, h, and d.The expansion and copy operations are handled explicitly, with an intermediate bound 2γ+h(d+2γ).
FO transductions: Map graphs have bounded twin-width because they are obtainable from planar graphs by first-order transductions.The paper also notes bounded twin-width for k-planar graphs and bounded-degree string graphs.
FO interpretations: A prenex first-order interpretation of a bounded-twin-width class has bounded twin-width, with the bound depending on the formula and the original width bound.The proof refines the original d-partitions in a bounded way determined by the formula depth.
FO interpretations: For a formula of quantifier depth ℓ, equivalent vertices within a d-partition split into at most a function of d and ℓ many components.This bounded-component property supports the construction of homogeneous parts in the interpreted graph.
FO interpretations: Equivalent vertex pairs receive identical formula evaluations, and symmetry makes the corresponding refined parts homogeneous in the interpreted graph.The argument uses automorphisms of reductions of the model-checking tree to preserve formula truth.

9 Conclusion

The paper introduces twin-width, develops contraction-sequence algorithms for several bounded-twin-width classes, and obtains linear FPT-time FO model checking when a witness sequence is supplied. It closes with open problems on computing sequences, certifying large twin-width, and characterizing tractable classes.

Conclusion: The paper computes contraction sequences for several bounded-twin-width classes and uses them to decide first-order formulas in linear FPT time.The main algorithmic guarantee assumes that a suitable contraction sequence is available.
Open problems: Computing twin-width or useful contraction sequences on general graphs remains the most pressing open algorithmic question.The paper does not expect exact computation to be tractable, but seeks an approximation whose ratio depends only on twin-width.
Open problems: A weak dual for twin-width is still missing: current lower-bound certification requires checking mixed minors across all vertex orderings.The paper asks whether the universal quantification over orderings can be eliminated.
Open problems: The paper raises whether the bounded-versus-unbounded twin-width dichotomy characterizes tractable hereditary classes for first-order model checking.This connects twin-width to the conjecture that non-universal classes admit FPT first-order model checking.
Future directions: Future directions include structured matrices, expanders, small classes, polynomial expansion, finitely generated groups, additive combinatorics, and approximation algorithms.The paper records both conjectures and negative results across these directions, including bounded twin-width for some expanders and unbounded twin-width for others.