Induced matching treewidth and tree-independence number, revisited
Noga Alon, Martin Milanič, Paweł Rzążewski · 2025
Read Induced matching treewidth and tree-independence number, revisited by Noga Alon, Martin Milanič, Paweł Rzążewski (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-03864.txt.
Introduction
Noga Alon, Martin Milanic, and Pawel Rzazewski revisit two graph parameters built from tree decompositions: tree-independence number and induced matching treewidth. Each replaces ordinary bag size with a different measure, one using independent sets and the other using induced matchings touching a bag.
Induced matching treewidth never exceeds tree-independence number, yet complete bipartite graphs show the reverse gap can be huge. Earlier work bounded one by a function of the other when a fixed biclique is excluded, but the bound was exponential. Using the Kovari-Sos-Turan theorem, the authors improve that dependence for biclique-free graph classes. The note sharpens how closely the two parameters can be tied together.
Catalog record
| CREATOR | Noga Alon, Martin Milanič, Paweł Rzążewski |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 25 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-03864
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Induced matching treewidth and tree-independence number, revisited Noga Alon, Martin Milanič, Paweł Rzążewski Abstract We study two graph parameters defined via tree decompositions: tree-independence number and induced matching treewidth. Both parameters are defined similarly as treewidth, but with respect to different measures of a tree decomposition 𝒯 \mathcal{T} of a graph G G : for tree-independence number, the measure is the maximum size of an independent set in G G included in some bag of 𝒯 \mathcal{T} , while for the induced matching treewidth, the measure is the maximum size of an induced matching in G G such that some bag of 𝒯 \mathcal{T} contains at least one endpoint of every edge of the matching. While the induced matching treewidth of any graph is bounded from above by its tree-independence number, the family of complete bipartite graphs shows that small induced matching treewidth does not imply small tree-independence number. On the other hand, Abrishami, Briański, Czyżewska, McCarty, Milanič, Rzążewski, and Walczak [SIAM Journal on Discrete Mathematics, 2025] showed that, if a fixed biclique K t , t K_{t,t} is excluded as an induced subgraph, then the tree-independence number is bounded from above by some function of the induced matching treewidth. The function resulting from their proof is exponential even for fixed t t , as it relies on multiple applications of Ramsey’s theorem. In this note we show, using the Kövári-Sós-Turán theorem, that for any class of K t , t K_{t,t} -free graphs, the two parameters are in fact polynomially related. 1 Introduction Treewidth is a graph parameter that, roughly speaking, measures how similar the graph is to a tree. The notion of treewidth was introduced independently several times and in different contexts (see [ 5 , 8 , 27 , 35 ] ) and has been an important tool in graph theory, for both structural as well as algorithmic reasons (see, e.g., [ 34 ] and [ 6 , 20 ] , respectively). The definition is based on the notion of a tree decomposition of a graph, that is, a collection of subsets of the vertex set of the graph called bags such that the endpoints of each edge of the graph appear in some bag, and, moreover, the bags are arranged in a tree so that the bags containing any fixed vertex of the graph form a nonempty subtree (see Section 2 for a precise definition). In the case of treewidth, the aim is to find a tree decomposition that minimizes the maximum size of a bag. One of the limitations of treewidth is that graphs with bounded treewidth are necessarily sparse. To overcome this limitation, several more general graph parameters have been defined in the literature that can also be bounded on dense graphs, while still retaining some of the good features of treewidth (see, e.g., [ 29 , 30 , 11 , 36 ] ). In particular, Yolov [ 36 ] and independently Dallard, Milanič, and Štorgel [ 24 ] introduced the notion of tree-independence number (denoted by \treealpha ), which is a graph parameter based on tree decompositions that is defined similarly as treewidth, but where instead of bounding the maximum size of a bag in a tree decomposition, what matters is the maximum size of an independent set contained in a bag. This parameter properly generalizes treewidth, as it can indeed capture dense graphs. For example, chordal graphs are known to admit tree decompositions such that every bag is a clique (see, e.g., [ 9 ] ); in other words, they have tree-independence number 1 . Classes of graphs with bounded tree-independence number have interesting structural properties (for example, treewidth of such graphs can only be large due to the presence of a large clique, see [ 24 ] ) and admit polynomial-time algorithms for several problems that are NP -hard on general graphs (see [ 22 , 24 , 32 , 36 , 14 ] ). However, some highly structured graphs, such as balanced complete bipartite graphs K_{t,t} , can have large treewidth even though they do not have large cliques; consequently, such graphs do not have bounded tree-independence number. This observation motivated Yolov [ 36 ] to introduce and study a further generalization of tree-independence number, called induced matching treewidth 1 1 1 Actually, Yolov defined this parameter for general hypergraphs and called it minor-matching hypertreewidth . The terminology and notation we use comes from the work of Lima et al. [ 32 ] , as it is more suitable to our setting. (and denoted by \yolov ), which is also based on tree decompositions, but the measure is the maximum size of an induced matching in the graph such that some bag of the tree decomposition intersects every edge of the matching. Induced matching treewidth generalizes tree-independence number, in the sense that bounded tree-independence number implies bounded induced matching treewidth. The generalization is proper: complete bipartite graphs, which have induced matching treewidth 1 but arbitrarily large tree-independence number, show that tree-independence number cannot be bounded from above by any function of induced matching treewidth. As shown already by Yolov [ 36 ] , classes of graphs with bounded induced matching treewidth enjoy some of the good algorithmic properties of graph classes of bounded tree-independence number. In particular, Lima, Milanič, Muršič, Okrasa, Rzążewski, and Štorgel (see [ 32 , 33 ] ) conjectured that classes with bounded induced matching treewidth admit a polynomial-time algorithm for a meta-problem defined by a fixed CMSO 2 -sentence \Phi and a fixed integer k , where for a given vertex-weighted graph G , the task is to find a maximum-weight set X\subseteq V(G) that induces a subgraph with treewidth at most k that satisfies \Phi . This conjecture was recently proved by Bodlaender, Fomin, and Korhonen [ 10 ] . From the structural point of view, both tree-independence number and induced matching treewidth have been studied in recent literature, see [ 2 , 33 ] for induced matching treewidth and [ 16 , 18 , 17 , 1 , 15 , 23 , 25 , 3 , 28 , 19 ] for tree-independence number. In particular, the two parameters were studied in relation to each other and to other width parameters, see [ 7 , 2 , 33 ] . For instance, Lima et al. [ 33 ] compared the two parameters in the context of (distance) powers of graphs, showing among other things that {\treealpha(G^{k})\leqslant\yolov(G)} for every odd integer k\geqslant 3 and every graph G with at least one edge. Furthermore, Abrishami, Briański, Czyżewska, McCarty, Milanič, Rzążewski, and Walczak [ 2 ] proved that for graph classes closed under induced subgraphs, complete bipartite graphs are the only reason why bounded induced matching treewidth does not imply bounded tree-independence number. Theorem 1.1 (Abrishami et al.) . For every two positive integers \mu and t , there is an integer \mathsf{K}(\mu,t) such that the following holds. Every K_{t,t} -free graph G with \yolov(G)\leqslant\mu satisfies \treealpha(G)<\mathsf{K}(\mu,t) . A systematic comparison of various graph width parameters under the assumption of excluding some K_{t,t} as a subgraph or induced subgraph was done recently by Brettell, Munaro, Paulusma, and Yang (see [ 13 ] ). Their work leaves open the