Hereditary graph classes have linked sublinear treewidth and separators
Clique-dependent strongly sublinear treewidth and strongly sublinear tree-independence number
Data Structures and Algorithms
Summary
Graphs are networks made of points (vertices) connected by lines (edges). Some graphs are easier to manage if they can be broken down using certain strategies, like tree decompositions. The authors study special groups of graphs (hereditary classes) and show that several complicated properties about breaking down these graphs without large connected chunks or big cliques are actually all equivalent. This means if one property holds, the others do too. They also provide an approach to efficiently find these break-down structures, which helps with algorithms that work on these graphs.
What this means in practice
- •For algorithm developers: Design subexponential-time algorithms for problems on hereditary graph classes using tree decompositions with small independent sets.
- •For network analysts: Apply clique-based balanced separators to analyze and simplify complex networks with bounded clique numbers for better computational management.
A theory result. No direct application yet.
Authors
Andrea Munaro
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 $\mathcal C$ with strongly sublinear tree-independence number admits a subexponential-time algorithm that, given $G\in\mathcal C$, computes a tree decomposition of $G$ with strongly sublinear independence number.