For some geometric graph classes, tractability of testing first-order formulas is precisely characterised by the graph parameter twin-width. This was first proved for interval graphs among others in [BCKKLT, IPEC '22], where the equivalence is called delineation, and more generally holds for circle graphs, rooted directed path graphs, and H-graphs when H is a forest. Delineation is based on the key idea that geometric graphs often admit natural vertex orderings, allowing to use the very rich theory of twin-width for ordered graphs. Answering two questions raised in their work, we prove that delineation holds for intersection graphs of non-degenerate axis-parallel unit segment graphs, but fails for visibility graphs of 1.5D terrains. We also prove delineation for intersection graphs of circular arcs.

Reduced parameters [BKW, JCTB '26; BKRT, SODA '22] are defined via contraction sequences. Based on this framework, we introduce the reduced component max-leaf, denoted by cml^↓, where component max-leaf is the maximum number of leaves in any spanning tree of any connected component. Reduced component max-leaf is strictly sandwiched between clique-width and reduced bandwidth, it is bounded in unit interval graphs, and unbounded in planar graphs. We design polynomial-time algorithms for problems such as Maximum Independent Set, Maximum Clique, Maximum Induced d-Regular Subgraph, and Induced Disjoint Paths in graphs given with a contraction sequence witnessing low cml^↓, unifying and extending tractability results for classes of bounded clique-width and unit interval graphs. We get the following collapses in sparse classes of bounded cml^↓: bounded maximum degree implies bounded treewidth, whereas K_{t,t}-subgraph-freeness implies strongly sublinear treewidth; we show the latter, more generally, for classes of bounded reduced cutwidth. We establish the former result by showing that graphs with bounded cml^↓ admit balanced separators dominated by a bounded number of vertices. In contrast, there are graphs G of arbitrarily large girth and treewidth Θ(|V(G)|^{1/2}) such that cml^↓(G) ⩽ 3. We then showcase an application of the reduced parameters to establishing non-transducibility results. We prove that for most reduced parameters p^↓ (including reduced bandwidth), the family of classes of bounded p^↓ is closed under first-order transductions. We then answer a question of [BKW '26] by showing that the 3-dimensional grids have unbounded reduced bandwidth. As the class of planar graphs (or any class of bounded genus) has bounded reduced bandwidth [BKW '26], this reproves a recent result [GPP, LICS '25; HJ, LICS '25] that planar graphs do not first-order transduce the 3-dimensional grids.

Lokshtanov, Ramanujan, Saurabh, and Zehavi [ICALP 2018] proved that for any CMSO formula $ϕ$, testing $ϕ$ on arbitrary graphs can be reduced to testing it on $(q,k)$-unbreakable graphs for appropriate parameters. Their proof is non-constructive, and they ask whether it can be made constructive. We prove that this is impossible: specifically, the parameter $q$ cannot be a computable function of $ϕ$.

A signed tree model of a graph G is a compact binary structure consisting of a rooted binary tree whose leaves are bijectively mapped to the vertices of G, together with 2-colored edges xy, called transversal pairs, interpreted as bicliques or anti-bicliques whose sides are the leaves of the subtrees rooted at x and at y. We design an algorithm that, given such a representation of an unweighted n-vertex graph G with p transversal pairs, and given a source v ∈ V(G), computes a shortest-path tree rooted at v in G in time O(p log n). A wide variety of graph classes are such that for all n, their n-vertex graphs admit signed tree models with O(n) transversal pairs: for instance, those of bounded symmetric difference (hence, in particular, those of bounded flip-width, merge-width, twin-width, and degeneracy), more generally of bounded sd-degeneracy, as well as interval graphs. As applications of our Single-Source Shortest Path algorithm and new techniques, we - improve the runtime of the fixed-parameter algorithm for first-order model checking on graphs given with a witness of low merge-width from cubic [Dreier & Toruńczyk, STOC '25] to quadratic; - give an O(n² log n)-time algorithm for All-Pairs Shortest Path on graphs given with a witness of low merge-width, generalizing a result known for twin-width [Twin-Width III, SICOMP '24]; - significantly extend and simplify an O(n² log n)-time algorithm for multiplying two n × n matrices A, B of bounded twin-width in [Twin-Width V, STACS '23]: now A solely has to be an adjacency matrix of a graph of bounded twin-width and B can be arbitrary; - give an O(n² log² n)-time algorithm for All-Pairs Shortest Path on graphs of bounded twin-width, bypassing the need for contraction sequences in [Twin-Width III, SICOMP '24; Bannach et al. STACS '24]; - give an O(n^{7/3} log² n)-time algorithm for All-Pairs Shortest Path on graphs of symmetric difference O(n^{1/3}). The second and the last two items imply the same for Diameter, Radius, Eccentricity, Wiener Index, etc. The last three items do not assume any witness to be given as part of the input.

Bojańczyk, Pilipczuk, and Grohe [LICS '18] proved that for graphs of bounded linear clique-width, clique-width decompositions of small width can be produced by a CMSO transduction. We show that in the case of tournaments, a first-order transduction suffices. This implies that the logics CMSO and existential MSO are equivalent over bounded linear clique-width tournaments.

We show that for any permutation π there exists an integer kπ such that every permutation avoiding π as a pattern factorises as the composition of at most kπ separable permutations. In other words, every strict class C of permutations is contained in a bounded power of the class of separable permutations. This factorisation can be computed in linear time, for any fixed π.

Abstract. We recently introduced the notion of twin-width, a novel graph invariant, and showed that first-order model checking can be solved in time [Formula: see text] for [Formula: see text]-vertex graphs given with a witness that the twin-width is at most [Formula: see text], called [Formula: see text]-contraction sequence or [Formula: see text]-sequence, and formulas of size [Formula: see text] [Bonnet et al., JACM ’22]. The inevitable price to pay for such a general result is that [Formula: see text] is a tower of exponentials of height roughly [Formula: see text]. In this paper, we show that algorithms based on twin-width need not be impractical. We present [Formula: see text]-time algorithms for [Formula: see text]-independent set, [Formula: see text]-scattered set, [Formula: see text]-clique, and [Formula: see text]-dominating set when an [Formula: see text]-sequence of the graph is given in input. We further show how to solve the weighted version of [Formula: see text]-independent set, subgraph isomorphism, and induced subgraph isomorphism in the slightly worse running time [Formula: see text]. Up to logarithmic factors in the exponent, all these running times are optimal unless the exponential time hypothesis fails. Like our first-order model checking algorithm, these new algorithms are based on a dynamic programming scheme following the sequence of contractions forward. We then show a second algorithmic use of the contraction sequence by starting at its end and rewinding it. As an example of such a reverse scheme, we present a polynomial-time algorithm that properly colors the vertices of a graph with relatively few colors, thereby establishing that bounded twin-width classes are [Formula: see text]-bounded. This significantly extends the [Formula: see text]-boundedness of bounded rank-width classes and does so with a very concise proof. It readily yields a constant approximation for max independent set on [Formula: see text]-free graphs of bounded twin-width and a [Formula: see text]-approximation for min coloring on bounded twin-width graphs. We further observe that a constant approximation for max independent set on bounded twin-width graphs (but arbitrarily large clique number) would actually imply a polynomial-time approximation scheme. The third algorithmic use of twin-width builds on the second one. Playing the contraction sequence backward, we show that bounded twin-width graphs can be edge-partitioned into a linear number of bicliques such that both sides of the bicliques are on consecutive vertices in a fixed vertex ordering. This property is trivially shared with graphs of bounded average degree. Given that biclique edge-partition, we show how to solve the unweighted single-source shortest paths, and hence all-pairs shortest paths, in time [Formula: see text] and time [Formula: see text], respectively. In sharp contrast, even diameter does not admit a truly subquadratic algorithm on bounded twin-width graphs unless the strong exponential time hypothesis fails. The fourth algorithmic use of twin-width builds on the so-called versatile tree of contractions [Bonnet et al., Comb. Theory ’22], a branching and more robust witness of low twin-width. We present constant-approximation algorithms for min dominating set and related problems on bounded twin-width graphs by showing that the integrality gap is constant. This is done by going down the versatile tree and stopping according to a problem-dependent criterion. At the reached node, a greedy approach yields the desired approximation.

International audience

A graph is Ok-free if it does not contain k pairwise vertex-disjoint and non-adjacent cycles. We show that MAXIMUM INDEPENDENT SET and 3-COLORING in Ok-free graphs can be solved in quasi-polynomial time. As a main technical result, we establish that “sparse” (here, not containing large complete bipartite graphs as subgraphs) Ok-free graphs have treewidth (even, feedback vertex set number) at most logarithmic in the number of vertices. This is proven sharp as there is an infinite family of O2-free graphs without K3,3-subgraph and whose treewidth is (at least) logarithmic. Other consequences include that most of the central NP-complete problems (such as MAXIMUM INDEPENDENT SET, MINIMUM VERTEX COVER, MINIMUM DOMINATING SET, MINIMUM COLORING) can be solved in polynomial time in sparse Ok-free graphs, and that deciding the Ok-freeness of sparse graphs is polynomial time solvable. * This work was supported by the ANR projects DISTANCIA (ANR-17-CE40-0015), DIGRAPHS (ANR-19-CE48-0013-01), and TWIN-WIDTH (ANR-21-CE48-0014-01), by the LabEx PERSYVAL-lab (ANR-11-LABX-0025), and by the Vanier Canada Graduate Scholarships program. † The full version of the paper can be accessed at https://arxiv.org/abs/2206.00594

We recently introduced the graph invariant twin-width, and showed that first-order model checking can be solved in time $f(d,k)n$ for $n$-vertex graphs given with a witness that the twin-width is at most $d$, called $d$-contraction sequence or $d$-sequence, and formulas of size $k$ [Bonnet et al., FOCS '20]. The inevitable price to pay for such a general result is that $f$ is a tower of exponentials of height roughly $k$. In this paper, we show that algorithms based on twin-width need not be impractical. We present $2^{O(k)}n$-time algorithms for $k$-Independent Set, $r$-Scattered Set, $k$-Clique, and $k$-Dominating Set when an $O(1)$-sequence is provided. We further show how to solve weighted $k$-Independent Set, Subgraph Isomorphism, and Induced Subgraph Isomorphism, in time $2^{O(k \log k)}n$. These algorithms are based on a dynamic programming scheme following the sequence of contractions forward. We then show a second algorithmic use of the contraction sequence, by starting at its end and rewinding it. As an example of this reverse scheme, we present a polynomial-time algorithm that properly colors the vertices of a graph with relatively few colors, establishing that bounded twin-width classes are $\chi$-bounded. This significantly extends the $\chi$-boundedness of bounded rank-width classes, and does so with a very concise proof. The third algorithmic use of twin-width builds on the second one. Playing the contraction sequence backward, we show that bounded twin-width graphs can be edge-partitioned into a linear number of bicliques, such that both sides of the bicliques are on consecutive vertices, in a fixed vertex ordering. Given that biclique edge-partition, we show how to solve the unweighted Single-Source Shortest Paths and hence All-Pairs Shortest Paths in sublinear time $O(n \log n)$ and time $O(n^2 \log n)$, respectively.

The recently introduced twin-width of a graph G is the minimum integer d such that G has a d-contraction sequence, that is, a sequence of |V(G)| – 1 iterated vertex identifications for which the overall maximum number of red edges incident to a single vertex is at most d, where a red edge appears between two sets of identified vertices if they are not homogeneous in G (not fully adjacent nor fully non-adjacent). We show that if a graph admits a d-contraction sequence, then it also has a linear-arity tree of f(d)-contractions, for some function f. Informally if we accept to worsen the twin-width bound, we can choose the next contraction from a set of Θ(|V(G)|) pairwise disjoint pairs of vertices. This has two main consequences. First it permits to show that every bounded twin-width class is small, i.e., has at most n!cn graphs labeled by [n], for some constant c. This unifies and extends the same result for bounded treewidth graphs [Beineke and Pippert, JCT '69], proper subclasses of permutations graphs [Marcus and Tardos, JCTA '04], and proper minor-free classes [Norine et al., JCTB '06]. It implies in turn that bounded-degree graphs, interval graphs, and unit disk graphs have unbounded twin-width. The second consequence is an O(log n)-adjacency labeling scheme for bounded twin-width graphs, confirming several cases of the implicit graph conjecture. We then explore the small conjecture that, conversely, every small hereditary class has bounded twin-width. The conjecture passes many tests. Inspired by sorting networks of logarithmic depth, we show that logΘ(log log d) n-subdivisions of Kn (a small class when d is constant) have twin-width at most d. We obtain a rather sharp converse with a surprisingly direct proof: the logd+1 n-subdivision of Kn has twin-width at least d. Secondly graphs with bounded stack or queue number (also small classes) have bounded twin-width. These sparse classes are surprisingly rich since they contain certain (small) classes of expanders. Thirdly we show that cubic expanders obtained by iterated random 2-lifts from K4 [Bilu and Linial, Combinatorica '06] also have bounded twin-width. These graphs are related to so-called separable permutations and also form a small class. We suggest a promising connection between the small conjecture and group theory. Finally we define a robust notion of sparse twin-width. We show that for a hereditary class of bounded twin-width the five following conditions are equivalent: every graph in (1) is Kt,t-free for some fixed t, (2) has an adjacency matrix without a d-by-d division with a 1 entry in each d2 cells for some fixed d, (3) has at most linearly many edges, (4) the subgraph closure of has bounded twin-width, and (5) has bounded expansion. We discuss how sparse classes with similar behavior with respect to clique subdivisions compare to bounded sparse twin-width.