Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number
Daniel Lokshtanov, Michał Pilipczuk, Paweł Rzążewski · 2026
Read Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number by Daniel Lokshtanov, Michał Pilipczuk, Paweł Rzążewski (2026) 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-2601-15861.txt.
Introduction
Daniel Lokshtanov, Michał Pilipczuk, and Paweł Rzążewski hunt for large sparse patterns in graphs in a 2026 arXiv paper. Their measure is the tree-independence number. Start with a tree decomposition of a graph. Its independence number is the largest independent set inside one bag. The graph's tree-independence number is the minimum of that value over decompositions. Recent work by Lima and others set up this frame.
The authors look for large sparse induced subgraphs. They target graphs whose tree-independence number is small, but not very small. That middle zone is where the theory gets hard. Induced subgraphs keep only chosen vertices and their links. Finding big sparse ones inside structured graphs feeds algorithm design. Such results often unlock faster methods for hard graph problems.
Catalog record
| CREATOR | Daniel Lokshtanov, Michał Pilipczuk, Paweł Rzążewski |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-15861
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number Daniel Lokshtanov, Michał Pilipczuk, Paweł Rzążewski Abstract The independence number of a tree decomposition is the size of a largest independent set contained in a single bag. The tree-independence number of a graph G G is the minimum independence number of a tree decomposition of G G . As shown recently by Lima et al. [ESA 2024], a large family of optimization problems asking for a maximum-weight induced subgraph of bounded treewidth, satisfying a given CMSO 2 property, can be solved in polynomial time in graphs whose tree-independence number is bounded by some constant k k . However, the complexity of the algorithm of Lima et al. grows rapidly with k k , making it useless if the tree-independence number is superconstant. In this paper we present a refined version of the algorithm. We show that the same family of problems can be solved in time n 𝒪 ( k ) n^{\mathcal{O}(k)} , where n n is the number of vertices of the instance, k k is the tree-independence number, and the 𝒪 ( ⋅ ) \mathcal{O}(\cdot) -notation hides factors depending on the treewidth bound of the solution and the considered CMSO 2 property. This running time is quasipolynomial for classes of graphs with polylogarithmic tree-independence number; several such classes were recently discovered. Furthermore, the running time is subexponential for many natural classes of geometric intersection graphs – namely, ones that admit balanced clique-based separators of sublinear size. 1 Introduction Tree decompositions and treewidth are among most successful concepts in graph theory, with numerous structural [ 34 , 37 , 14 , 10 ] and algorithmic applications [ 10 , 5 , 9 ] (see Section 2.1 for formal definitions). In the context of the latter, having a tree decomposition of a graph with small (say, constant) width allows us to mimic the standard bottom-up dynamic programming on trees in order to solve many computational problems efficiently. This idea led to a flurry of algorithmic results and techniques, designed for graphs of bounded treewidth [ 22 , 29 , 6 , 30 , 7 ] . In order to understand which problems can be solved efficiently on given class of graphs, it is beneficial to design algorithms that do not focus on particular problems, but rather on families of problems expressible in a certain way. Such results are typically referred to as algorithmic meta-theorems . On a high level, an algorithmic meta-theorem says that every problem of a given type can be solved efficiently in the given class of graphs. Such “types of problems” are usually defined in terms of logic. Probably the best known algorithmic meta-theorem is the celebrated result of Courcelle [ 21 ] which says that every problem expressible in \mathsf{CMSO}_{2} can be solved in linear time in graphs given with a tree decomposition of constant width. Here, \mathsf{CMSO}_{2} is the Monadic Second Order logic of graphs with quantification over edge subsets and modular predicates. In essence, the logic allows quantification over single vertices and edges as well as over subsets of vertices and of edges. See Section 2.2 for more information on \mathsf{CMSO}_{2} and the result of Courcelle. While Courcelle’s theorem handles a very broad family of problems, it comes at a cost: the assumption that the treewidth is bounded by a constant is rather restrictive. In particular, the theorem applies only to sparse graphs. On the other hand, there are classes of dense graphs with very good structural properties, like interval graphs [ 33 , Chapter 8] , circular-arc graphs [ 33 , Chapter 8.6] , or chordal graphs [ 33 , Chapter 4] . Often these properties can be expressed in terms of the existence of a certain tree decomposition whose every bag has some “nice structure” (opposed to every bag having bounded size, as in the definition of treewidth). For instance, chordal graphs are precisely the graphs that admit a tree decomposition where every bag is a clique. Such decompositions with a “nice structure” can be also exploited algorithmically. This motivation led to the definition of tree-independence number of a graph. This parameter was independently introduced by Yolov [ 39 ] and by Dallard et al. [ 25 ] ; we use the notation and terminology from the latter work. The independence number of a tree decomposition is the minimum value of k such that every bag induces a subgraph of independence number at most k . The tree-independence number of a graph G is the minimum independence number of a tree decomposition of G ; see Section 2.1 for more information. Thus, chordal graphs are exactly graphs of tree-independence number 1. The algorithmic motivation behind the definition of tree-independence number was to understand the tractability of the Max (Weight) Independent Set problem ( MWIS ). Indeed, a standard dynamic programming approach shows that MWIS can be solved in polynomial time for graphs of bounded tree-independence number, given with an appropriate tree decomposition. However, it turns out that many other problems, asking for finding large induced subgraphs that are sparse (or, equivalently in this context, of bounded clique number), can be efficiently solved in the considered classes [ 39 ] . In particular, many of these problems can be expressed as special cases of a certain abstract problem. For an integer t and a \mathsf{CMSO}_{2} sentence \psi , we define (\mathrm{tw}<t,\psi) - MWIS (here, MWIS stands for maximum-weight induced subgraph ) as follows. Input: A graph G equipped with a weight function \mathfrak{w}\colon V(G)\to\mathbb{Q}_{+} . Task: Find a set F\subseteq V(G) , such that • G[F]\models\psi , • \mathrm{tw}(G[F])<t , and • F is of maximum weight subject to the conditions above, or conclude that no such set exists. (\mathrm{tw}<t,\psi) - MWIS Notable special cases of the (\mathrm{tw}<t,\psi) - MWIS problem are MWIS , Feedback Vertex Set (equivalently, Max Induced Forest ), and Even Cycle Transversal (equivalently, Max Induced Odd Cactus ). As shown by Lima et al. [ 35 ] , every problem expressible as (\mathrm{tw}<t,\psi) - MWIS can be efficiently solved in graphs of bounded tree-independence number (given with a decomposition). Theorem 1.1 (Lima et al. [ 35 ] ) . For any fixed integers t,k and a fixed \mathsf{CMSO}_{2} sentence \psi , there exists d such that the following holds: The (\mathrm{tw}<t,\psi) - MWIS problem can be solved in time \mathcal{O}(n^{d}) in n -vertex graphs of tree-independence number at most k . Let us remark that the assumption that the solution induces a sparse graph is crucial here. In particular, Clique is NP -hard in graphs of tree-independence number 2, as MWIS is NP -hard in triangle-free graphs [ 36 ] . Interestingly, algorithms for (\mathrm{tw}<t,\psi) - MWIS are known also for other classes of well-structured dense graphs [ 2 , 32 , 19 , 31 ] . Theorem 1.1 allows us to solve a rich family of optimization problems in classes of constant tree-independence number [ 26 , 1 ] . However, the fact that the exponent d depends (at least) exponentially on k makes the algorithm from Theorem 1.1 not very useful for classes where tree-independence is small, but superconstant –