Tree independence number V. Walls and claws

Abstract

Given a family $\mathcal{H}$ of graphs, we say that a graph $G$ is $\mathcal{H}$-free if no induced subgraph of $G$ is isomorphic to a member of $\mathcal{H}$. Let $S_{t,t,t}$ be the graph obtained from $K_{1,3}$ by subdividing each edge $t-1$ times, and let $W_{t\times t}$ be the $t$-by-$t$ hexagonal grid. Let ${\mathcal{L}}_t$ be the family of all graphs $G$ such that $G$ is the line graph of some subdivision of $W_{t\times t}$. We prove that for every positive integer $t$ there exists $c(t)$ such that every ${\mathcal{L}}_t\cup \{S_{t,t,t},K_{t,t}\}$-free $n$-vertex graph admits a tree decomposition in which the maximum size of an independent set in each bag is at most $c(t){\log }^{4}n$. This is a variant of a conjecture of Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht from 2024. This implies that the Maximum Weight Independent Set problem, as well as many other natural algorithmic problems, that are known to be NP-hard in general, can be solved in quasi-polynomial time if the input graph is ${\mathcal{L}}_t\cup \{S_{t,t,t},K_{t,t}\}$-free. As part of our proof, we show that for every positive integer $t$ there exists an integer $d$ such that every ${\mathcal{L}}_t\cup \{S_{t,t,t}\}$-free graph admits a balanced separator that is contained in the neighborhood of at most $d$ vertices.