Clique-dependent strongly sublinear treewidth and strongly sublinear tree-independence number
Abstract
We establish a strongly sublinear counterpart of a recent result of Chudnovsky, E S, and Lokshtanov (arXiv 2025) on treewidth and tree-independence number. Namely, we prove that a hereditary graph class has strongly sublinear tree-independence number if and only if, for every fixed clique bound, its graphs of bounded clique number have strongly sublinear treewidth. In fact, this is part of a broader equivalence theorem. For hereditary classes, these conditions are also equivalent to having clique-dependent polynomial expansion, to admitting balanced separators whose size is bounded by Kω(G)s |V(G)|1−β for fixed K,s,β>0, and to admitting balanced clique-based separators of strongly sublinear size (equivalently, weight). Thus, we show that all these properties, which arose independently in the study of subexponential-time exact algorithms and polynomial-time approximation schemes, in fact describe the same hereditary graph classes. As a consequence of our equivalence theorem, we also show that every hereditary class 𝒞 with strongly sublinear tree-independence number admits a subexponential-time algorithm that, given G∈𝒞, computes a tree decomposition of G with strongly sublinear independence number.
Related
- QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators
- Stochastic wave equations driven by space-time G-white noise under sublinear expectation
- Sublinear Michaux-Villemaire over (ℕ, +, kN)
- Invariance principle for long-memory linear processes under sublinear expectations
- Classification of radially symmetric solutions to a Hardy-Hénon equation with sublinear absorption and applications
BibTeX
@misc{munaro2026cliquedependent,
title = {{Clique-dependent strongly sublinear treewidth and strongly sublinear tree-independence number}},
author = {Andrea Munaro},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.24684},
eprint = {2609.24684},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.24684},
}
RIS
TY - UNPB
TI - Clique-dependent strongly sublinear treewidth and strongly sublinear tree-independence number
AU - Andrea Munaro
PY - 2026
DA - 2026/09/21
PB - arXiv
DO - 10.48550/arxiv.2609.24684
UR - https://arxiv.org/abs/2609.24684
AB - We establish a strongly sublinear counterpart of a recent result of Chudnovsky, E S, and Lokshtanov (arXiv 2025) on treewidth and tree-independence number. Namely, we prove that a hereditary graph class has strongly sublinear tree-independence number if and only if, for every fixed clique bound, its graphs of bounded clique number have strongly sublinear treewidth. In fact, this is part of a broader equivalence theorem. For hereditary classes, these conditions are also equivalent to having clique-dependent polynomial expansion, to admitting balanced separators whose size is bounded by Kω(G)^s |V(G)|^1−β for fixed K,s,β>0, and to admitting balanced clique-based separators of strongly sublinear size (equivalently, weight). Thus, we show that all these properties, which arose independently in the study of subexponential-time exact algorithms and polynomial-time approximation schemes, in fact describe the same hereditary graph classes. As a consequence of our equivalence theorem, we also show that every hereditary class 𝒞 with strongly sublinear tree-independence number admits a subexponential-time algorithm that, given G∈𝒞, computes a tree decomposition of G with strongly sublinear independence number.
ER -