Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909997858816000 |
|---|---|
| author | Lokshtanov, Daniel Pilipczuk, Michał Rzążewski, Paweł |
| author_facet | Lokshtanov, Daniel Pilipczuk, Michał Rzążewski, Paweł |
| contents | 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$ is the minimum independence number of a tree decomposition of $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 \textsf{CMSO}$_2$ property, can be solved in polynomial time in graphs whose tree-independence number is bounded by some constant~$k$.
However, the complexity of the algorithm of Lima et al. grows rapidly with $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^{\mathcal{O}(k)}$, where $n$ is the number of vertices of the instance, $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 \textsf{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_15861 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number Lokshtanov, Daniel Pilipczuk, Michał Rzążewski, Paweł Data Structures and Algorithms 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$ is the minimum independence number of a tree decomposition of $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 \textsf{CMSO}$_2$ property, can be solved in polynomial time in graphs whose tree-independence number is bounded by some constant~$k$. However, the complexity of the algorithm of Lima et al. grows rapidly with $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^{\mathcal{O}(k)}$, where $n$ is the number of vertices of the instance, $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 \textsf{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. |
| title | Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2601.15861 |