Induced packing treewidth

In this paper, we introduce a framework that aims to unify classes defined by forbidden induced subgraphs or induced minors with classes defined by the existence of certain structured tree decompositions.

Let $\mathcal{H}$ be a fixed family of graphs.

We define \emph{induced-$\mathcal{H}$-packing treewidth}, a tree-decomposition-based graph parameter that, for each bag, measures the maximum number of pairwise anticomplete induced copies of graphs from $\mathcal{H}$ intersecting that bag.

This notion generalizes some previously studied parameters: when $\mathcal{H}=\{P_1\}$, it is equivalent to tree-independence number, and when $\mathcal{H}=\{P_2\}$, it is equivalent to induced matching treewidth.

We show that bounded induced-$\mathcal{H}$-packing treewidth yields new algorithmic consequences for a range of choices of $\mathcal{H}$.

In particular, we prove the following results for graphs of bounded induced-$\mathcal{H}$-packing treewidth.

Our results partially answer and substantially extend a question of Bodlaender, Fomin, and Korhonen [SODA~2026] on the tractability of \textsc{MWIS} for graphs of bounded induced-$\mathcal{H}$-packing treewidth for $\mathcal{H}=\{P_3\}$ and for $\mathcal{H}$ equal to the family of all cycles.