Abstract 1 Introduction 2 Preliminaries 3 The Eleven 4 FO logic 5 Bounds on 𝗻𝗲𝗰 in terms of 𝓕-branchwidth 6 Independent Set parameterized by 𝓕-Branchwidth References

On Algorithmic Applications of ℱ-Branchwidth

Benjamin Bergougnoux ORCID Aix-Marseille Université, LIS, CNRS, France Thekla Hamm ORCID TU Eindhoven, The Netherlands Lars Jaffke ORCID NHH Norwegian School of Economics, Bergen, Norway Paloma T. Lima ORCID IT University of Copenhagen, Denmark
Abstract

ℱ-branchwidth is a framework for width measures of graphs, recently introduced by Eiben et al. [ITCS 2022], that captures tree-width, co-tree-width, clique-width, and mim-width, and several of their generalizations and interpolations. In this work, we search for algorithmic applications of ℱ-branchwidth measures that do not have an equivalent counterpart in the literature so far. Our first contribution is a minimal set of eleven ℱ-branchwidth measures such that each of the infinitely many ℱ-branchwidth measures is equivalent to one of the eleven. We observe that for the FO Model Checking problem, each ℱ-branchwidth is either equivalent to clique-width (and therefore has an 𝖥𝖯𝖳-algorithm by formula length plus the width) or the problem remains as hard as on general graphs even on graphs of constant width. Next, we study the number of equivalence classes of the neighborhood equivalence in a decomposition, which upper bounds the run time of the model checking algorithm for 𝖠&𝖢⁢𝖣𝖭 logic recently introduced by Bergougnoux et al. [SODA 2023]. We give structural lower bounds that show that for each ℱ-branchwidth, an efficient model checking algorithm was already known or cannot be obtained via this method. Lastly, we classify the complexity of Independent Set parameterized by any ℱ-branchwidth except for one open case. Also here, our contributions are lower bounds. In this context, we also prove that Independent Set on graphs of mim-width w cannot be solved in time no⁢(w) unless the Exponential Time Hypothesis fails, answering an open question in the literature.

Keywords and phrases:
Graph width parameters, parameterized complexity, F-branchwidth, tree-width, clique-width, rank-width, mim-width, FO model checking, DN logic, Independent Set, ETH
Funding:
Thekla Hamm: Supported during part of this research by the Austrian Science Fund FWF project number J4651.
Paloma T. Lima: Supported by the Independent Research Fund Denmark grant agreement number 2098-00012B.
Copyright and License:
[Uncaptioned image] © Benjamin Bergougnoux, Thekla Hamm, Lars Jaffke, and Paloma T. Lima; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation → Graph algorithms analysis ; Mathematics of computing → Graph algorithms
Acknowledgements:
We thank Édouard Bonnet for the proof strategy behind Lemma 41.
Related Version:
A full version of the paper is currently in preparation.
DOI:
10.4230/LIPIcs.ESA.2025.16
Event:
33rd Annual European Symposium on Algorithms (ESA 2025)
Editors:
Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman
Series and Publisher:
LIPIcs Logo Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Eiben et al. [12] recently introduced ℱ-branchwidth, a framework of graph width measures that allows for an infinite number of instantiations. Among them are width measures that are asymptotically equivalent to treewidth, clique-width, and mim-width. These three have wide algorithmic applications which immediately begs the following question:

Are there any unknown ℱ-branchwidth measures that have interesting algorithmic applications?

The goal of this paper is to address this question – to which we provide negative answers in several contexts.

For a family of bipartite graphs ℱ, the ℱ-branchwidth of a graph G bounds the size of any member of ℱ that appears as a semi-induced subgraph in a recursive partitioning of the vertex set of G. Therefore, any family of bipartite graphs ℱ gives rise to a new ℱ-branchwidth measure. To avoid chaotic definitions, some technical restrictions are imposed on ℱ, but there is still an infinite number of families ℱ satisfying them. However, as already observed in [12], there is a finite number of classes of ℱ-branchwidth measures that are bounded on different families of graphs. This means that we can restrict the search for new algorithmically useful width measures to the representatives of these classes. These are obtained as any combination of the six families shown in Figure 1.

Figure 1: The six canonical families usable as building blocks for ℱ-branchwidth. From left to right: edgeless (), complete (), matchings (), antimatchings (), chains (), and skewed chains ().

This brings down the number of cases to consider from infinite to constant, if one wants to determine the complexity of a problem parameterized by any of the possible ℱ-branchwidth measures. However, a priori there are still 26 cases to consider. Our first contribution is to provide a family of eleven ℱ-branchwidth, called The Eleven, that captures the modeling power of every possible ℱ-branchwidth in the following sense. For an illustration see Figure 2.

Theorem 1.

For each ℱ-branchwidth, one of the following holds.

  1. (i)

    There is a computable function f such that for each graph G with ℱ-𝖻𝗐⁢(G)≤k, |V⁢(G)|≤f⁢(k).

  2. (ii)

    ℱ-branchwidth is asymptotically equivalent to ℱ∗-branchwidth, where ℱ∗ is one of the Eleven branchwidths (presented in Figure 2 and formally defined in Table 1).

We provide families of obstructions to bounded width that show that the classification in Theorem 1 is in fact minimal, in the sense that no pair of width measures can be asymptotically equivalent to each other.

Theorem 2.

For each pair of distinct ℱ1,ℱ2∈𝔉 there is some i∈[2] such that there is a graph class of bounded ℱi-width but unbounded ℱ3−i-width.

Throughout the following, we refer to the ℱ-branchwidth measures based on the families in 𝔉 as the canonical ones. Notice that the second item of Theorem 1 says that ℱ-branchwidth and ℱ∗-branchwidth are bounded on the same graph classes, but the exact bounds may differ. Theorem 1, along with the hierarchy among the eleven relevant width measures, allows us to determine the complexity of a problem parameterized by any ℱ-branchwidth by considering these cases alone.

Figure 2: The Eleven canonical ℱ-branchwidth measures, ordered according to expressive power from top (high) to bottom (low). The five base cases show the singleton classes, and bold edges show combinations. For instance, chim-width is (∪)-branchwidth, clique⋆-width is (∪∪)-branchwidth, and tree⋆-width is (∪)-branchwidth. The remaining edges show some relationships given by the structures of the families. As one may expect, tree⋆-width is asymptotically equivalent to tree-width, clique⋆-width is asymptotically equivalent to clique-width, and co-tree⋆-width is asymptotically equivalent to co-tree-width.

A common way to classify the algorithmic power of a width measure is to determine for which logic 𝖫, the 𝖫-Model Checking problem can be solved efficiently whenever the input graph is given together with a decomposition of constant width. For instance, an 𝖫-formula ϕ may express that a graph has an independent set of size k. Then, the evaluation of ϕ at a graph G is true, in symbols G⊧ϕ (read: “G models ϕ”), if and only if G has an independent set of size k. Typically, one aims for efficient parameterized algorithms in the parameterization formula length plus width.

𝖫-Model Checking

Input: Graph G given together with a decomposition of width w, 𝖫-formula ϕ.
Question: Does G⊧ϕ?

Classical examples of such meta-theorems are Courcelle’s Theorem [8] which gives an 𝖥𝖯𝖳-algorithm when 𝖫 is 𝖬𝖲𝖮2 logic and the width is tree-width and its extension to the more general clique-width while restricting the logic to 𝖬𝖲𝖮1 [9]. More recent examples include an 𝖥𝖯𝖳-algorithm for 𝖥𝖮 logic and twin-width [6], and an 𝖷𝖯-algorithm for 𝖠&𝖢⁢𝖣𝖭 logic and mim-width [3]. The following hierarchy holds for the first three logics: 𝖥𝖮⊊𝖬𝖲𝖮1⊊𝖬𝖲𝖮2.

We consider the Model Checking problem for any of these logics parameterized by any of the ℱ-branchwidth measures. Our first result is that for 𝖬𝖲𝖮/𝖥𝖮, we cannot expect any new tractability islands via ℱ-branchwidth, so in fact, our current understanding of the complexity of 𝖬𝖲𝖮/𝖥𝖮 Model Checking is tight for any ℱ-branchwidth. We illustrate the following theorem for the canonical ℱ-branchwidth measures in Figure 3.

Theorem 3.

For each ℱ-branchwidth, one of the following holds.

  1. 1.

    There is a computable function f such that each graph of ℱ-branchwidth k has clique-width at most f⁢(k), implying that 𝖥𝖮 Model Checking is 𝖥𝖯𝖳 parameterized by formula length plus k.

  2. 2.

    There is a constant c such that 𝖥𝖮 Model Checking parameterized by formula length is 𝖠𝖶⁢[∗]-hard even when the input graph is given with one of its decompositions of ℱ-branchwidth c.

Next, we move on to 𝖠&𝖢⁢𝖣𝖭 logic which was recently introduced by Bergougnoux et al. [3] as a logic to capture the problems that are solvable in 𝖷𝖯 time parameterized by the mim-width of a given decomposition of the input graph. This logic is a good target to study under the lens of ℱ-branchwidth. It is the right fit for mim-width which is -branchwidth where is the family of matchings – one of the base families of ℱ-branchwidth. 𝖠&𝖢⁢𝖣𝖭 logic is essentially111The neighborhood operator in [3] is somewhat more general, but for the sake of this introduction it suffices to think of simple neighborhoods. based on existential 𝖬𝖲𝖮1 and a neighborhood operator which, for a given set variable X, returns the set ⋃v∈XN⁢(v), and predicates checking acyclicity and connectivity. The runtime of the algorithm for 𝖠&𝖢⁢𝖣𝖭 Model Checking is bounded by the index of the neighborhood equivalence relation (𝗇𝖾𝖼), first studied by Bui-Xuan et al. [7].To get efficient algorithms, it therefore suffices to show, for graphs of width k, that the index of the neighborhood equivalence grows relatively slowly in terms of n and k. For instance, a bound of f⁢(k)⋅n𝒪⁢(1) implies an f⁢(k)⋅n𝒪⁢(1) time algorithm for 𝖠&𝖢⁢𝖣𝖭 Model Checking, while a bound of ng⁢(k) implies an n𝒪⁢(g⁢(k)) time algorithm, using the meta-theorem of [3].

Several such bounds on the index of this equivalence relation are already known in the literature. First, mim-width k implies that there are at most nk equivalence classes [2]. Furthermore, there are bounds of the form 2𝒪⁢(k) when k is either the tree-width, clique-width, or co-tree-width (see, for instance, [3]). Next, we cannot hope to obtain any meaningful bound for any ℱ-branchwidth that generalizes complete-width. When a cut consists of matching with n vertices on each side, the complete-width is just 1, while the number of neighborhoods across the cut is 2n. Indeed, for each subset of vertices contained in one side of the cut, there is a different subset across the cut whose neighborhood is exactly that subset.

The cases that remain are the ones asymptotically equivalent to empty-width, chim-width, and mam-width. As mim-width generalizes all of them, we immediately have 𝖷𝖯-algorithms parameterized by each of them. Also here, we provide a number of negative results. For chim-width and mam-width, not much improvement can be made over the bound given by mim-width. We show that there are graphs of chim-width (or mam-width) k such that each of their decompositions induces a cut with at least (n/(k2⁢log⁡n))Ω⁢(k) neighborhoods. By a probabilistic argument, we show that there are graphs whose decompositions have cuts of empty-width k that have nΩ⁢(k) neighborhoods. We conclude that the technology from [3] cannot be applied directly to any ℱ-branchwidth measure to extend the range of tractability of 𝖠&𝖢⁢𝖣𝖭 Model Checking, see Figure 3 for an illustration.

Theorem 4.

For each ℱ-branchwidth, one of the following holds.

  1. 1.

    There is a computable function f such that each graph of ℱ-branchwidth k has clique-width at most f⁢(k), implying that 𝖠&𝖢⁢𝖣𝖭 Model Checking is 𝖥𝖯𝖳 parameterized by formula length plus the width of a given decomposition of the input graph.

  2. 2.

    Each graph of ℱ-branchwidth k has mim-width at most k, implying that 𝖠&𝖢⁢𝖣𝖭 Model Checking is 𝖷𝖯 parameterized by formula length plus the width of a given decomposition of the input graph. On the other hand, there are cuts of ℱ-branchwidth k with nΩ⁢(k) neighborhood equivalence classes.

  3. 3.

    There is a computable function f such that each graph of complete-width at most k has ℱ-branchwidth at most f⁢(k), implying that there are cuts on n vertices of constant ℱ-branchwidth with 2Ω⁢(n) neighborhood equivalence classes.

Figure 3: Results about the complexity of model checking problems on graphs of bounded ℱ-branchwidth. Left: Complexity of 𝖥𝖮 Model Checking. Right: Number of neighborhoods in cuts of bounded width.

For the canonical ℱ-branchwidth measures, we also take a more fine-grained look at the index of the neighborhood equivalence. The upper bounds on the number of equivalence classes in terms of clique⋆-width and tree⋆-width follow from known bounds [3] together with Ramsey-theory based arguments from [12]. This results in upper bounds that are double-exponential in the width k, i.e., bounds of the form 22𝗉𝗈𝗅𝗒⁢(k). For tree⋆-width and co-tree⋆-width k, we give improved, single-exponential, bounds of 2𝒪⁢(k3⁢log⁡k) each, and a lower bound of 2Ω⁢(k⁢log⁡k) for tree⋆-width k.

For the lower bound statements of Theorem 4, observe two things. First, for chim-width and mam-width, the bounds in fact hold for any decomposition of graphs within a family we construct. Second, lower bounds on the number of equivalence classes of the neighborhood equivalence only rule out direct applications of the meta-theorem from [3], and are not hardness results per se.

Figure 4: The complexity of Independent Set parameterized by any ℱ-branchwidth measure. Note that the complexity of Independent Set parameterized by empty-width is still open, but the 𝖷𝖯 lower bound on the number of equivalence classes in the neighborhood equivalence implies that known techniques are not applicable to show fixed-parameter tractability in this case. Moreover, it is worth looking into the complexity of IS parameterized by solution size on graphs of constant miam-width, cham-width, or complete-width.

Due to that, we explicitly consider the Independent Set and Dominating Set problems as two of the most fundamental problems expressible in 𝖠&𝖢⁢𝖣𝖭 logic. Here, we provide several new hardness results. First, we show 𝖶⁢[1]-hardness parameterized by chim-width and mam-width, and we show that under the Exponential Time Hypothesis, no no⁢(k) time algorithm can exist. The latter gives a negative answer to the question explicitly asked for instance in [1, 4] whether the linear dependence on the mim-width in the exponent of the algorithms from [7] can be lowered significantly.

Theorem 5.

Unless the Exponential Time Hypothesis fails, neither Independent Set nor Dominating Set can be solved in f⁢(k)⁢no⁢(k) time for any computable function f, where k is either the chim-width, the mam-width, or the mim-width of a given decomposition of the n-vertex input graph. Moreover, both problems parameterized by either the chim-width or the mam-width are 𝖶⁢[1]-hard.

Since Independent Set is 𝖭𝖯-complete on cubic graphs, it is para-𝖭𝖯-hard when parameterized by any width measure in whose obstructions the degree increases proportionally to the size. This is the case for complete bipartite graphs, anti-matchings, and chains. However, one might hope for efficient algorithms for Independent Set parameterized by solution size on graphs of constant width. For chain-width, we rule out this possibility by proving that the graphs from a reduction due to Fomin, Golovach, and Raymond [13] have bounded chain-width.

Theorem 6.

Independent Set parameterized by solution size is 𝖶⁢[1]-hard even when the input graph is provided with a linear decomposition of chain-width 3.

We summarize the results for the Independent Set problem in Figure 4.

This paper is organized as follows. In the next section, we introduce our notations and the ℱ-branchwidths framework, as wells as some basics facts on these parameters. Theorem 2 is proved in Section 3. Theorem 3 is proved in Section 4. Theorem 4 is proved in Section 5. Finally, Theorem 5 is proved in Section 5. Missing proofs are in the full version.

2 Preliminaries

For an integer i, we let [i]={1,2,…,i}.

We use standard graph terminology and notation [11], some of which we briefly recall in the following. In every notation with a graph subscript, we may omit it if the graph is clear from the context.

A cut of a graph G is a partition of V⁢(G) into two sets A,B. We denote by G⁢[A,B] the subgraph of G with edge set {u⁢v∈E⁢(G)∣u∈A,v∈B}. A graph G is bipartite if it can be written as G⁢[A,B] for some cut A,B. In this case we also use (A,B,E) to denote G. If |A|=|B|, then we call |V(G)/2|(=|A|=|B|) the half-order of G.

For a graph G, its (edge) complement G¯ is given by (V⁢(G),{u⁢v∣u,v∈V⁢(G)∧v⁢w∉E⁢(G)}). Given a set A⊆V⁢(G), we use A¯ as shorthand for V⁢(G)∖A. For a bipartite graph G=(A,B,E), its bipartite (edge) complement is given by (A,B,{u⁢v∣u∈A∧v∈B∧u⁢v∉E}).

Branch decomposition.

A branch decomposition or tree layout (or simply layout) of a graph G is a pair (T,λ) where T is a ternary tree (i.e., every internal node of T has degree 3) and λ is a bijection from V⁢(G) to the leaves of T. An edge e of T induces or defines a cut (Xe,Ye) of G, where Xe and Ye are the preimages by λ of the leaves in the two components of T−e. For a symmetric function 𝖿G:2V⁢(G)→ℤ which we refer to as a cut function of G, the 𝖿-width of e is 𝖿G⁢(Xe), the 𝖿-width of the branch decomposition T is the maximum width over all edges of T, and the 𝖿-branchwidth of G, denoted by 𝖿⁢0⁢p⁢t⁢(G), is the minimum width of a branch decomposition of G.

The following lemma encapsulates a standard argument on branch decompositions that we need to obtain some of our lower bound results.

Lemma 7.

Let G be a graph and X⊆V⁢(G) such that |X|≥2. Any branch decomposition of G has an edge that displays a bipartition (L,R) of V⁢(G) so that |L∩X|≥|X|/3 and |R∩X|≥|X|/3.

Corresponding linear branchwidth constrains T to be a path with a pendant for each internal node. The linear 𝖿-branchwidth of G is denoted by 𝗅𝗂𝗇⁢-⁢𝖿⁢0⁢p⁢t⁢(G). It is equivalent to view the layout given by such a tree as a permutation of V⁢(G) where the considered cuts for linear branchwidth are between vertices before and vertices after each point in the permutation.

Besides ℱ-branchwidth, we will also use the cut function 𝗇𝖾𝖼G (and its associated branchwidth) defined as follows. Given A⊆V⁢(G), two subsets X and Y of A are neighborhood-equivalent over A if N⁢(X)∖A=N⁢(Y)∖A, we define 𝗇𝖾𝖼G⁢(A) as the number of equivalence relation over A.

We focus on the branchwidths proposed in [12] that arise as follows. Let ℱ be an infinite family of bipartite graphs where each graph in ℱ has bipartition (A=(a1,…,an),B=(b1,…,bn)) such that for each 2⁢n-vertex graph in ℱ and each subset L of [n], the graph induced on {ai,bi|i∈L} is isomorphic to a graph in ℱ. Given a graph G, we define the ℱ-cut function 𝖿G of G such that 𝖿G⁢(X) is the the largest k such that a 2⁢k-vertex graph in ℱ is isomorphic to an induced subgraph of G⁢[X,V⁢(G)∖X]. It is known that for any such choice of ℱ, ℱ-branchwidth is asymptotically equivalent to ℱ′-branchwidth where ℱ′ is a union of any of the following six graph classes which are called si ph (short for size identifiable partner hereditary): the class of all bipartite induced matchings, the class of all bipartite complements of induced matchings, also called antimatchings (or co-matchings), the class of all complete bipartite graphs with an equal number of vertices on each side of the bipartition, the class of all bipartite edgeless graphs with an equal number of vertices on each side of the bipartition, which we simply refer to as bipartite edgeless graphs, the class of all bipartite graphs with an equal number of vertices on each side of the bipartition such that the vertices on each side permit an indexing under which each vertex u on one side has an edge to a vertex v other the index of u is at most the index of v, which we refer to as chains, and the class of all bipartite graphs with an equal number of vertices on each side of the bipartition such that the vertices on each side permit an indexing under which each vertex u on one side has an edge to a vertex v other the index of u is less than the index of v, which we refer to as skewed chains.

It will be useful to introduce the following notation for some bipartite graphs:

  • ■

    k=((a1,…,ak),(b1,…,bk),E), where E=∅.

  • ■

    k=((a1,…,ak),(b1,…,bk),E), where E={ai⁢bj∣i,j∈[k]}.

  • ■

    k=((a1,…,ak),(b1,…,bk),E), where E={ai⁢bi∣i∈[k]}.

  • ■

    k=((a1,…,ak),(b1,…,bk),E), where E={ai⁢bj∣i,j∈[k],i≠j}.

  • ■

    k=((a1,…,ak),(b1,…,bk),E), where E={ai⁢bj∣1≤i≤j≤k}.

  • ■

    k=((a1,…,ak),(b1,…,bk),E), where E={ai⁢bj∣1≤i<j≤k}.

2.1 Co-/degeneracy, empty-width/complete-width, and subdivisions

In this subsection, we explore the relations between degeneracy [16], subdivisions, complete-width and empty-width. All the corollary of this subsection follows from the fact that the (linear) complete-width of a graph is exactly the (linear) empty-width of its complement. This will be useful to establish relationships between ℱ-branchwidths in the next section.

Proposition 8.

Let G be a graph with degeneracy at most k. Then, G has linear complete-width at most k.

Corollary 9.

Let G be a graph with co-degeneracy at most k. Then, G has linear empty-width at most k.

On the other hand, hypercubes have unbounded degeneracy but complete-width at most 2.

Proposition 10.

For each d∈ℕ, the hypercube of dimension d has minimum degree d and linear complete-width at most two.

Corollary 11.

For each d∈ℕ, the hypercube of dimension d has minimum co-degree d and linear empty-width at most two.

For a graph G and a positive integer q, the q-subdivision of G is the graph obtained from G by subdividing each edge q times.

Observation 12.

Let G be a simple graph, and let G′ be obtained from G by subdividing each edge at least once. Then, any linear ordering of G′ has complete-width at most one.

Corollary 13.

Let G be a simple graph and let G′¯ be the complement of a graph obtained from G by subdividing each edge at least once. Then, any linear ordering of G′ has empty-width at most one.

3 The Eleven

In this section we show that we can restrict ourselves further to eleven different ℱ-branchwidth measures, called the Eleven (shown in Figure 2) and still obtain complete classifications. We begin by restating a lemma from [12] to justify that we do not need to consider the family of skewed chains.

Lemma 14 (Lemma 4.9 in [12]).

Let ℱ be a union of si ph classes. If ⊆ℱ, then for every graph G it holds that |ℱ⁢-𝖻𝗐⁢(G)−ℱ′⁢-𝖻𝗐⁢(G)|≤1, where ℱ′=(ℱ∖)∪.

The remaining five singleton-classes that we restrict our attention to from now on are each interesting in their own right. The following observation will come in useful.

Observation 15.

Let H=((a1,…,ak),(b1,…,bk),E) be an ordered bipartite graph.

  1. 1.

    If H=k, then H contains an edgeless bipartite graph of half-order ⌊k/2⌋.

  2. 2.

    If H=k or H=k, then H contains an edgeless bipartite graph of half-order ⌊k/2⌋.

  3. 3.

    If H=k, or H=k, or H=k, then H contains a complete bipartite graph of half-order ⌊k/2⌋.

We move on to pairs, first observing that we can restrict ourselves to the case when at most one of or is contained in ℱ.

Lemma 16.

Let ℱ be a union of si ph classes such that ∪⊆ℱ. There is a computable function f such that for each graph G with ℱ-𝖻𝗐⁢(G)≤k, |V⁢(G)|<f⁢(k).

When ⊆ℱ, the presence or absence of or in ℱ does not matter asymptotically either.

Lemma 17.

Let ℱ be a union of si ph classes such that ⊆ℱ. Let ℱ∗ be any (possibly empty) combination of {,}, and let ℱ′=ℱ∪ℱ∗. Then, for any graph G, ℱ-𝖻𝗐⁢(G)≤ℱ′⁢-𝖻𝗐⁢(G)≤2⋅ℱ-𝖻𝗐⁢(G)+1.

Similarly, we have the following.

Lemma 18.

Let ℱ be a union of si ph classes such that ⊆ℱ. Let ℱ∗ be any (possibly empty) combination of {,}, and let ℱ′=ℱ∪ℱ∗. Then, for any graph G, ℱ-𝖻𝗐⁢(G)≤ℱ′⁢-𝖻𝗐⁢(G)≤2⋅ℱ-𝖻𝗐⁢(G)+1.

We are now ready to define the Eleven– see Table 1 – and prove Theorem 1.

Table 1: Definitions of the Eleven ℱ-branchwidth and introduction of the notations for their associated ℱ-cut functions.
ℱ Name ℱ-cut function ℱ Name ℱ-cut function
complete-width 𝖼𝗈𝗆𝗉𝗅𝖾𝗍𝖾G ∪ tree⋆-width 𝗍⋆G
empty-width 𝖾𝗆𝗉𝗍𝗒G ∪ co-tree⋆-width 𝖼𝗈⁢-⁢𝗍⋆G
mim-width 𝗆𝗂𝗆G ∪ mam-width 𝗆𝖺𝗆G
miam-width 𝗆𝗂𝖺𝗆G ∪ chim-width 𝖼𝗁𝗂𝗆G
chain-width 𝖼𝗁𝖺𝗂𝗇G ∪ cham-width 𝖼𝗁𝖺𝗆G
∪∪ clique⋆-width 𝖼⋆G

Observe that tree⋆-width is asymptotically equivalent to tree-width and clique⋆-width is asymptotically equivalent [12, Section 4].

Theorem 1. [Restated, see original statement.]

For each ℱ-branchwidth, one of the following holds.

  1. (i)

    There is a computable function f such that for each graph G with ℱ-𝖻𝗐⁢(G)≤k, |V⁢(G)|≤f⁢(k).

  2. (ii)

    ℱ-branchwidth is asymptotically equivalent to ℱ∗-branchwidth, where ℱ∗ is one of the Eleven branchwidths (presented in Figure 2 and formally defined in Table 1).

Next, we argue that the relationships between the Eleven as shown in Figure 2 indeed faithfully represent their hierarchy. That is, whenever two width measures are connected, then the one on top strictly generalizes the one the bottom, and whenever there is no connection (in terms of paths) between two, then they are incomparable. The fact that the depicted generalizations hold up follows directly from the definition and in some cases Observation 15.

For the lower bounds on width measures, we need the following canonical classes of graphs of unbounded width. For each n∈ℕ, we consider the following graphs on vertex set [n]×[n].

  • ■

    The n×n grid, denoted by n, has edges {(i,j),(i′,j′)} where |i−i′|+|j−j′|=1.

  • ■

    The complement of the n×n grid is denoted by ¯n.

  • ■

    The n×n comparability grid, denoted by n, has edges {(i,j),(i′,j′)} where i≤i′ and j≤j′. For an illustration see Figure 5. Note that comparability grids appear in the study of rank-width naturally [15].

Figure 5: Illustration of comparability grids by the example of 5. On the left, the grid structure plus the additional edges incident with one highlighted vertex. In the middle and on the right, some chains that appear in cuts of a branch decomposition.

Grids have unbounded mim-width [17], which in the language of ℱ-branchwidth can be expressed in a more general form as follows.

Proposition 19.

Let ℱ be a union of si ph families. If (∪)∩ℱ≠∅, then for each n∈ℕ, ℱ-𝖻𝗐⁢(n)∈Ω⁢(n).

By complementation, we have the following consequence.

Corollary 20.

Let ℱ be a union of si ph families. If (∪)∩ℱ≠∅, then for each n∈ℕ, ℱ-𝖻𝗐⁢(¯n)∈Ω⁢(n).

Lastly, we show that comparability grids are a family of unbounded chain-width, while their mam-width is bounded by a constant.

Proposition 21.

For each n∈ℕ, 𝗅𝗂𝗇⁢-⁢𝗆𝖺𝗆⁢0⁢p⁢t⁢(n)=1 and 𝖼𝗁𝖺𝗂𝗇⁢0⁢p⁢t⁢(n)≥n/4.

Next, we observe upper bounds on ℱ-branchwidth of grids, their complements, and comparability grids.

Proposition 22.

Let ℱ be a union of si ph families. If ℱ⊆∪∪, then, for each n∈ℕ, ℱ-𝖻𝗐⁢(n)∈𝒪⁢(1).

By complementation and Corollary 9, we get the following.

Corollary 23.

Let ℱ be a union of si ph families. If ℱ⊆∪∪, then, for each n∈ℕ, ℱ-𝖻𝗐⁢(¯n)∈𝒪⁢(1).

Table 2: Each cell shows families of graphs whose width is bounded by a constant by the width measure whose cut-function indexes the row and unbounded by the width measure whose cut-function indexes the column. Here, stands for the family of grids, ¯ for the complements of grids, and for the comparability grids. For instance, the entry in row “𝖼𝗁𝖺𝗂𝗇” and column “𝗆𝗂𝗆” indicates that the family of grids has constant chain-width but unbounded mim-width. Furthermore, Kn denotes the family of complete graphs, and ∅n the family of edgeless graphs.
𝖼𝗁𝖺𝗂𝗇 𝗆𝗂𝗆 𝗆𝗂𝖺𝗆 𝖼𝗁𝗂𝗆 𝗆𝖺𝗆 𝖼𝗁𝖺𝗆 𝖾𝗆𝗉𝗍𝗒 𝖼𝗈𝗆𝗉𝗅𝖾𝗍𝖾 𝖼⋆/𝗍⋆/𝖼𝗈⁢-⁢𝗍⋆
𝖼𝗁𝖺𝗂𝗇 ¯ ¯ ¯ ¯ ¯
𝗆𝗂𝗆 ¯ ¯ ¯ ¯ ¯
𝗆𝗂𝖺𝗆
𝖼𝗁𝗂𝗆 ¯ ¯ ¯ ∅n ¯ ¯
𝗆𝖺𝗆
𝖼𝗁𝖺𝗆 Kn
𝖾𝗆𝗉𝗍𝗒 ¯ ¯ ¯ ¯ ¯
𝖼𝗈𝗆𝗉𝗅𝖾𝗍𝖾
𝖼⋆ ∅n Kn / Kn / ∅n
𝗍⋆ ∅n / / ∅n
𝖼𝗈⁢-⁢𝗍⋆ Kn / Kn /

Using Propositions 19, 20, 21, 22, and 23, we can argue almost all of the desired relationships, see Table 2. The remainder is discussed in the full version which concludes the proof of Theorem 2.

4 FO logic

It is known that 𝖥𝖮 Model Checking is 𝖠𝖶⁢[∗]-hard on interval graphs [14]. Furthermore, interval graphs are known to have linear mim-width 1, witnessed by a linear order that can be computed in polynomial time [2]. Next, we can observe that for any graph G and A⊆V⁢(G),

𝗆𝗂𝗆G⁢(A)≤1⇔𝗆𝗂𝖺𝗆G⁢(A)≤1.

This is because a matching of half-order 2 and an anti-matching of half-order 2 are isomorphic. Therefore, we have the following consequence.

Corollary 24 (of [2, 14]).

𝖥𝖮-Model Checking parameterized by the length of the formula is 𝖠𝖶⁢[∗]-hard on graphs of linear mam-width one, even if a width-1 linear order of the input graph is given.

Due to Corollary 24, the only remaining cases where we could hope for 𝖥𝖯𝖳-algorithms for 𝖥𝖮-Model Checking are complete-width and empty-width. However, we show by two trivial reductions that the problem remains 𝖶[1]-hard parameterized by formula length on graphs of width 1 as well. Note that the following reduction is folklore, but we state it here for completeness.

Proposition 25.

𝖥𝖮-Model Checking parameterized by the length of the formula is 𝖠𝖶⁢[∗]-hard on graphs of linear complete-width one, even if a width-1 linear order of the input graph is given.

Let (G,ϕ) be an instance of 𝖥𝖮-Model Checking such that G has linear complete-width one. Observe that G¯ has linear empty-width one. We replace each occurrence of xi∼xj in ϕ with ¬xi∼xj to obtain a formula ϕ′. Then, G¯⊧ϕ′ if and only if G⊧ϕ and we obtain the following.

Corollary 26.

𝖥𝖮-Model Checking parameterized by the length of the formula is 𝖠𝖶⁢[∗]-hard on graphs of linear empty-width one, even if a width-1 linear order of the input graph is given.

5 Bounds on 𝗻𝗲𝗰 in terms of 𝓕-branchwidth

The run time of the algorithm for 𝖠&𝖢⁢𝖣𝖭 Model Checking from [3] is polynomial in the number of equivalence classes of the neighborhood equivalence relation. Therefore, any bound on this quantity immediately translates to an efficient algorithm for 𝖠&𝖢⁢𝖣𝖭 Model Checking.

5.1 Upper Bounds

We first give some upper bounds. For tree-width, co-tree-width, and clique-width, single-exponential upper bounds on 𝗇𝖾𝖼 are known (e.g., [3]). Pipelined through the arguments from [12], this gives bounds for the equivalent ℱ-branchwidth parameters, but they might end up double-exponential due to the Ramsey arguments in [12]. Here, we give single-exponential upper bounds in terms of these width parameters by giving more direct arguments.

Lemma 27.

Let G be a graph and A⊆V⁢(G) such that 𝗍⋆G⁢(A)≤k. Let M be a matching in G⁢[A,A¯]. Then, |M|<(k+1)k+2.

Lemma 28.

Let G be a graph, A⊆V⁢(G) with 𝗍⋆G⁢(A)≤k. There is a set Ω⊆A of size at most 2𝒪⁢(k2⁢log⁡k) such that {N⁢(v)∩A¯∣v∈A}={N⁢(v)∩A¯∣v∈Ω}.

Proposition 29.

Let G be a graph and A⊆V⁢(G) with 𝗍⋆G⁢(A)≤k. Then, 𝗇𝖾𝖼G⁢(A)∈2𝒪⁢(k3⁢log⁡k).

Proposition 30.

Let G be a graph and A⊆V⁢(G) with 𝖼𝗈⁢-⁢𝗍⋆G⁢(A)≤k. Then, 𝗇𝖾𝖼G⁢(A)≤2𝒪⁢(k3⁢log⁡k).

5.2 Lower bounds

We first exhibit some cuts with high 𝗇𝖾𝖼 in terms of the respective width parameters. Later, we then prove that there are families of graphs where each of their branch decompositions has to have a cut with large 𝗇𝖾𝖼.

Observation 31.

Let G be obtained by taking the disjoint union of an antimatching with 2⁢n vertices and a matching with 2⁢k vertices and completely connecting the sides A and A¯ of the resulting bipartite graph. It holds that 𝖾𝗆𝗉𝗍𝗒⁢0⁢p⁢t⁢(G)≤k, and 𝗇𝖾𝖼G⁢(A)≥2k⋅n.

For the following observation, take the disjoint union of k chains of half-order k.

Observation 32.

There is a bipartite graph G=(A,B,E) with 𝗍⋆G⁢(A)=k and 𝗇𝖾𝖼G⁢(A)∈2Ω⁢(k⁢log⁡k).

Observation 33.

Let H=Hn with bipartition (A,B). Then, 𝗇𝖾𝖼H⁢(A)=2n.

Observation 34.

For each n∈ℕ there is a graph G on 2⁢n vertices and A⊆V⁢(G) such that 𝖼𝗈𝗆𝗉𝗅𝖾𝗍𝖾G⁢(A)=1 and 𝗇𝖾𝖼G⁢(A)=2n.

Proposition 35.

There is an infinite family of graphs G with 𝖼𝗈𝗆𝗉𝗅𝖾𝗍𝖾⁢0⁢p⁢t⁢(G)=1 and such that each branch decomposition of G induces a cut (A,A¯) with 𝗇𝖾𝖼G⁢(A)∈2Ω⁢(|V⁢(G)|).

Proposition 36.

For each n,k∈ℕ with n≥k there is a bipartite graph G=(A,B,E) on 2⁢n vertices such that 𝗆𝖺𝗆G⁢(A)=k and 𝗇𝖾𝖼G⁢(A)=⌊n/k⌋k.

By taking a disjoint union of k antimatchings of half-order n/k in the previous proof, we get the following corollary.

Corollary 37.

For each n,k∈ℕ with n≥k there is a bipartite graph G=(A,B,E) on 2⁢n vertices such that 𝖼𝗁𝗂𝗆G⁢(A)=k and 𝗇𝖾𝖼G⁢(A)=⌊n/k⌋k.

In the following, we provide several lower bounds on the 𝗇𝖾𝖼-width of graphs of low chim-width, mam-width, tree⋆-width, or co-tree⋆-width. The proofs strategy are based on the proof of [5, Theorem 1.3] stating that there exists arbitrary large graphs of rank-width k with Boolean-width Ω⁢(k2).

We start by proving a lower bound on 𝗇𝖾𝖼-width in terms of chim-width. The following construction is based on the reduction used to prove Theorem 5 for chim-width.

Lemma 38.

For each k∈ℕ with k>0, there exist arbitrary large graphs G of linear chim-width at most 2⁢k and with 𝗇𝖾𝖼⁢0⁢p⁢t⁢(G)∈(n/(k2⁢log⁡n))Ω⁢(k).

It is easy to obtain the same result as Lemma 38 for mam-width by replacing anti-matchings by chains in the construction of the graph G.

Lemma 39.

For each k∈ℕ with k>0, there exist arbitrary large graphs G of linear mam-width at most k+1 and with 𝗇𝖾𝖼⁢0⁢p⁢t⁢(G)∈(n/(k2⁢log⁡n))Ω⁢(k).

Lemma 40.

For each k∈ℕ with k>0, there exist arbitrary large graphs G of linear tree⋆-width at most 2⁢k and with 𝗇𝖾𝖼⁢0⁢p⁢t⁢(G)∈kΩ⁢(k).

Lemma 41.

For each n,k∈ℕ with n sufficiently large, there is a graph G=(A,B,E) on 2⁢n vertices such that 𝖾𝗆𝗉𝗍𝗒⁢0⁢p⁢t⁢(G)≤k and with 𝗇𝖾𝖼⁢0⁢p⁢t⁢(G)∈|V⁢(G)|Ω⁢(k).

6 Independent Set parameterized by 𝓕-Branchwidth

In this section, we discuss the complexity of Independent Set parameterized by any ℱ-branchwidth measure. On top of that, we strengthen known hardness results for Independent Set and Dominating Set (full version) on graphs of bounded mim-width under the ETH. Concretely, we show the following.

Theorem 5. [Restated, see original statement.]

Unless the Exponential Time Hypothesis fails, neither Independent Set nor Dominating Set can be solved in f⁢(k)⁢no⁢(k) time for any computable function f, where k is either the chim-width, the mam-width, or the mim-width of a given decomposition of the n-vertex input graph. Moreover, both problems parameterized by either the chim-width or the mam-width are 𝖶⁢[1]-hard.

These lower bounds are tight because the algorithm – based on the d-neighbor equivalence – from [7] solves Independent Set and Dominating Set in time nO⁢(w) where w is the mim-width of a given decomposition which is always smaller than its chim-width and mam-width.

It is well-known that Independent Set is 𝖥𝖯𝖳 parameterized by clique-width, and therefore clique⋆-width, so for all ℱ-branchwidth measures that are at most as general as clique⋆-width, Independent Set is 𝖥𝖯𝖳.

6.1 Independent Set on graphs of bounded complete-width and chain-width

Since Independent Set is 𝖭𝖯-complete on cubic graphs, it is 𝗉𝖺𝗋𝖺𝖭𝖯⁢-⁢𝗁𝖺𝗋𝖽 when parameterized by any width measure in whose obstructions the degree increases proportionally to the size. This is the case for complete bipartite graphs, anti-matchings, and chains.

Observation 42.

Independent Set is 𝖭𝖯-hard on graphs with complete-width at most 3.

Nevertheless, the previous result does not rule out efficient parameterized algorithms for Independent Set when the solution size is an additional part of the parameter. Note that here, the bounded-degree argument does not apply, since Independent Set parameterized by solution size plus maximum degree can easily be shown to be 𝖥𝖯𝖳 [10]. However, we show that Independent Set remains 𝖶⁢[1]-hard parameterized by solution size on graphs of (the more general) chain-width at most 3. (The same reduction in fact shows 𝖶⁢[1]-hardness parameterized by solution size plus chim-width.)

This can be shown by observing that the graphs obtained in the reduction that proved 𝖶⁢[1]-hardness for Independent Set parameterized by mim-width plus solution size [13] in fact have a linear order whose mim-width is bounded by a function of the parameter and whose chim-width is at most three.

Corollary 43.

Independent Set is W[1]-hard parameterized by

  • ■

    the solution size (plus the linear mim-width) on graphs of linear chain-width 3, or

  • ■

    the solution size plus the linear chim-width

of the input graph, even if a linear order of bounded width is provided with the input.

6.2 Independent Set on graphs of bounded chim-width

To prove Theorem 5 for chim-width and Independent Set, we provide a reduction from Multicolored Independent Set in general graphs to Independent Set in graphs of low chim-width. Briefly, an instance of Multicolored Independent Set consists of a graph whose vertex set is the disjoint union of k sets V1,…,Vk and the problem asks for a multicolored independent set which is an independent set with exactly one vertex in each Vi. Let H a graph with V⁢(H)=V1⊎⋯⊎Vk be an instance of Multicolored Independent Set. We denote by N the number of vertices of H and by M the number of edges of H. In the following, we show how to construct in polynomial time a graph G with at most n=N⁢M vertices and a linear order of chim-width at most 2⁢k such that H admits a multicolored independent set iff G admits an independent set of size at least k⁢M. This is sufficient to prove Theorem 5 for chim-width. Indeed, with a f⁢(w)⁢no⁢(w) time algorithm for Independent Set for some computable function f, we would be able to solve Multicolored Independent Set in time f⁢(k)⁢No⁢(k) which is not possible under the ETH [10]. Futhermore, the 𝖶⁢[1]-hardness of Independent Set parameterized by chim-width follows from the 𝖶⁢[1]-hardness of Multicolored Independent Set parameterized by k [10].

Intuitively, we start by creating a selection gadget Su⁢v for each edge u⁢v of H such that the maximum independent sets of G⁢[Su⁢v] are bijectively mapped to the potential solution of H – set of vertices with exactly one vertex in each Vi – which do not contains both u and v. Then we glue the selection gadgets together in such a way that the maximum independent sets in two glued gadgets are non-adjacent if and only if they are associated with the same potential solution of H. See Figure 6 for an illustration of the following construction.

Figure 6: Illustration of the reduction for chim-width with k=3, V1={1,2,3,4}, V2={5,6,7} and V3={8,9}. Here M=3 and the edges of H consists of e1=45, e2=48 and e3=68. Dashed lines represent the non-edges of the anti-matchings between the selection gadgets. To improve the legibility, we omit the edges of the cliques Seij: i,j∈[3]. The independent set I consisting of the white filled vertices have size k⁢M and IH={2,7,8} is a multicolored independent set of H.

Selection gadgets.

For each edge e∈E⁢(H), we create the selection gadget Se which consists of the disjoint union of k cliques Se1,…,Sek such that for each j∈[k], Sei . . ={xe∣x∈Vi}. We finish the construction of Se by adding the edge between ue and ve where u and v are the endpoints of e. Given a set X⊆Se, we denote by XH the set {x∈V⁢(H)∣xe∈X}.

Observation 44.

For every edge e of H, X is a maximum independent set I of G⁢[Se] if and only if XH has exactly one vertex in each Vi and does not contain both endpoints of e.

Propagation.

The final step of this construction is to add edges between the selection gadgets such that if H admits a multicolored independent sets then every maximum independent set I of G intersects the selections gadgets in the same way, i.e. for every pair of edges (e1,e2) of H, we have (I∩Se1)H=(I∩Se2)H. We achieve this without blowing up the chim-width of G as follows. We fix an edge e1 of H and for every edge e≠e1 of H and i∈[k], we first add all the edges between Se1i and Sei and then for each vertex x∈Vi, we remove the edge xe1⁢xe. Consequently, the bipartite graph G⁢[Se1i⁢Sei] is an anti-matching of half-order |Vi|. As Se1i and Sei are cliques in G, the maximum independent sets of G⁢[Se1i∪Sei] are exactly the pairs {xe1,xe} with x∈Vi. This leads to the following observation.

Observation 45.

For every edge e≠e1 of H and subsets X,Y of size k of respectively Se1 and Se, there is no edge between X and Y in G if and only if we have XH=YH.

We deduce from Observations 44 and 45 the correctness of our reduction.

Lemma 46.

The graph G admits an independent set of size at least k⁢M if and only if H admits a multicolored independent set.

Finally, we prove that we can construct in polynomial time a linear order of G of chim-width at most 2⁢k+2. The following proof relies on the fact that induced matchings and chains in anti-matchings have size at most 2, which implies that the chim-width of the cut (Se1,V⁢(G)∖Se1) is at most 2⁢k.

Lemma 47.

We can compute in polynomial time a linear order of G of chim-width at most 2⁢k+2.

6.3 Independent Set on graphs of bounded mam-width

The proof of Theorem 5 for mam-width is similar to the one for chim-width, we start from the same instance of Multicolored Independent Set and construct a graph G. Compared to chim-width, the following construction is a bit more involved and uses skewed chains instead of anti-matchings to glue the selection gadgets together. See Figure 7 for an illustration of the following construction.

Figure 7: Illustration of the reduction for mam-width with k=3, V1={1,2,3,4}, V2={5,6,7} and V3={8,9}. Here M=3 and the edges of H consists of e1=45, e2=48 and e3=68. To improve the legibility, we omit the edges of the cliques Seij: i,j∈[3]. Moreover, we represent only the non-edges (with dashed lines) of the anti-matchings between Se1 and Se2. The independent set I consisting of the white filled vertices have size k⁢M and IH={2,7,8} is a multicolored independent set of H.

Selection gadgets.

We reuse the selection gadget Se1,Se2⁢…,SeM from the reduction for chim-width where e1,…,eM are the edges of H.

Propagation.

First, we add anti-matchings between Se1 and Se2 just as we did in the reduction of chim-width. That is for every i∈[k], we do the following. We add all the edges between Se1i and Se2i. Finally, for every vertex v∈Vi, we remove the edge ve1⁢ve2. Note that G⁢[Se1i,Se2i] is big anti-matching, but this does not blow-up the mam-width. Indeed, we can insert in the permutation of Lemma 47 each vertex of Se2i next to its non-neighbor in Se1i, this way every cut of the resulting permutation contains at most one non-edge of G⁢[Se1i,Se2i] and the mam-width stays low. Note that Observation 45 holds for e=e2.

Finally, we add skewed chains between Se1∪Se2 and the other selection gadgets, by doing the following. We take a arbitrary strict linear order <H on the vertices of H such that for each i,j∈[k] with i<j, we have u<Hv for each u∈Vi and v∈Vj. For every i∈[M] with i>2, j∈[k], and x,y∈Vj such that x<Hy, we make xe1 adjacent to yei and ye2 adjacent to xei.

Observe that, for every i∈[M], j∈[t] and X∈{R,S}, the graphs G⁢[Se1j,Seij] and G⁢[Se2j,Seij] are skewed chain graphs of half-order |Vi|. Moreover, the maximum independent sets of G⁢[Se1j∪Se2j∪Seij] are exactly the sets {ve1,ve2,vei} with v∈Vi.

Observation 48.

For every i∈[M] and subsets X,Y and Z of respectively Se1,Se2 and Sei, each of size k, there is no edge between any two of these subsets in G if and only if XH=YH=ZH.

References

  • [1] Brage I. K. Bakkane and Lars Jaffke. On the hardness of generalized domination problems parameterized by mim-width. In Holger Dell and Jesper Nederlof, editors, 17th International Symposium on Parameterized and Exact Computation, IPEC 2022, September 7-9, 2022, Potsdam, Germany, volume 249 of LIPIcs, pages 3:1–3:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.IPEC.2022.3.
  • [2] Rémy Belmonte and Martin Vatshelle. Graph classes with structured neighborhoods and algorithmic applications. Theor. Comput. Sci., 511:54–65, 2013. doi:10.1016/j.tcs.2013.01.011.
  • [3] Benjamin Bergougnoux, Jan Dreier, and Lars Jaffke. A logic-based algorithmic meta-theorem for mim-width. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), pages 3282–3304. SIAM, 2023. doi:10.1137/1.9781611977554.ch125.
  • [4] Benjamin Bergougnoux and Mamadou Moustapha Kanté. More applications of the d-neighbor equivalence: Acyclicity and connectivity constraints. SIAM J. Discret. Math., 35(3):1881–1926, 2021. doi:10.1137/20M1350571.
  • [5] Benjamin Bergougnoux, Tuukka Korhonen, and Jesper Nederlof. Tight lower bounds for problems parameterized by rank-width. In Petra Berenbrink, Patricia Bouyer, Anuj Dawar, and Mamadou Moustapha Kanté, editors, 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023, March 7-9, 2023, Hamburg, Germany, volume 254 of LIPIcs, pages 11:1–11:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.STACS.2023.11.
  • [6] Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable FO model checking. J. ACM, 69(1):3:1–3:46, 2022. doi:10.1145/3486655.
  • [7] Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle. Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theoret. Comput. Sci., 511:66–76, 2013. doi:10.1016/j.tcs.2013.01.009.
  • [8] Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput., 85(1):12–75, 1990. doi:10.1016/0890-5401(90)90043-H.
  • [9] Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discret. Appl. Math., 108(1-2):23–52, 2001. doi:10.1016/S0166-218X(00)00221-3.
  • [10] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.
  • [11] Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012.
  • [12] Eduard Eiben, Robert Ganian, Thekla Hamm, Lars Jaffke, and O-joung Kwon. A unifying framework for characterizing and computing width measures. In Mark Braverman, editor, Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 63:1–63:23, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2022.63.
  • [13] Fedor V. Fomin, Petr A. Golovach, and Jean-Florent Raymond. On the tractability of optimization problems on H-graphs. Algorithmica, 82(9):2432–2473, 2020. doi:10.1007/s00453-020-00692-9.
  • [14] Robert Ganian, Petr Hlinený, Daniel Král, Jan Obdrzálek, Jarett Schwartz, and Jakub Teska. FO model checking of interval graphs. Log. Methods Comput. Sci., 11(4), 2015. doi:10.2168/LMCS-11(4:11)2015.
  • [15] Jim Geelen, O-joung Kwon, Rose McCarty, and Paul Wollan. The grid theorem for vertex-minors. J. Comb. Theory B, 158(Part):93–116, 2023. doi:10.1016/J.JCTB.2020.08.004.
  • [16] Don R. Lick and Arthur T. White. k-degenerate graphs. Canadian Journal of Mathematics, 22(5):1082–1096, 1970. doi:10.4153/CJM-1970-125-1.
  • [17] Martin Vatshelle. New Width Parameters of Graphs. PhD thesis, University of Bergen, Norway, 2012.