{"ID":6621239,"CreatedAt":"2026-07-15T01:01:48.440468303Z","UpdatedAt":"2026-07-15T03:28:55.185153975Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.12090","arxiv_id":"2607.12090","title":"Induced-Minor-Closed Classes have Linear, Square-Root, or Sub-Polynomial Tree-Independence","abstract":"An independent set in a graph $G$ is a set of pairwise non-adjacent vertices. A tree decomposition of $G$ is a pair $(T, χ)$ where $T$ is a tree and $χ: V(T) \\rightarrow 2^{V(G)}$ is a function satisfying two axioms: for every edge $uv \\in E(G)$ there is an $x \\in V(T)$ such that $\\{u,v\\} \\subseteq χ(x)$, and for every vertex $u \\in V(G)$ the set $\\{x \\in V(T) | u \\in χ(x)\\}$ induces a non-empty and connected subtree of $T$. The sets $χ(x)$ for $x \\in V(T)$ are called the bags of the tree decomposition. The tree-independence number of $G$ is the minimum taken over all tree decompositions of $G$ of the maximum size of an independent set of the graph induced by a bag of the decomposition. A graph $H$ is an induced minor of a graph $G$ if a graph isomorphic to $H$ can be obtained from $G$ by vertex deletions and edge contractions. We prove that for every $t\\in\\mathbb{N}$ there exists an $ε\u003e 0$ such that every graph $G$ either contains the complete bipartite graph $K_{t,t}$ or the wall $W_{t\\times t}$ as an induced minor, or has tree-independence at most $O(2^{O((\\log n)^{1-ε})})$. This leads to algorithms with running time $2^{n^{o(1)}}$, for a wide range of problems on $\\{K_{t,t}, W_{t\\times t}\\}$-induced minor free graphs. Our result is a substantial generalization of existing bounds for the tree-independence and tree-width on various graph classes, and a partial resolution of the conjecture of Chudnovsky, E S, and Lokshtanov [Arxiv, 2025] that $\\{K_{t,t}, W_{t\\times t}\\}$-induced minor free graphs have poly-logarithmic tree independence number. The generality comes at the cost of a sub-polynomial, rather than poly-logarithmic upper bound. Our result leads to a complete classification of induced-minor closed classes into ones that have sub-polynomial tree-independence, tree-independence equal to $\\tilde{O}(\\sqrt{n})$, and linear tree-independence.","short_abstract":"An independent set in a graph $G$ is a set of pairwise non-adjacent vertices. A tree decomposition of $G$ is a pair $(T, χ)$ where $T$ is a tree and $χ: V(T) \\rightarrow 2^{V(G)}$ is a function satisfying two axioms: for every edge $uv \\in E(G)$ there is an $x \\in V(T)$ such that $\\{u,v\\} \\subseteq χ(x)$, and for every...","url_abs":"https://arxiv.org/abs/2607.12090","url_pdf":"https://arxiv.org/pdf/2607.12090v1","authors":"[\"Maria Chudnovsky\",\"Julien Codsi\",\"Ajaykrishnan E S\",\"Daniel Lokshtanov\"]","published":"2026-07-13T19:10:36Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"cs.DM\",\"cs.DS\"]","methods":"[]","has_code":false}