{"ID":6138346,"CreatedAt":"2026-07-09T01:07:32.349475501Z","UpdatedAt":"2026-07-11T16:11:27.930961336Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.07595","arxiv_id":"2607.07595","title":"Induced packing treewidth","abstract":"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.","short_abstract":"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-dec...","url_abs":"https://arxiv.org/abs/2607.07595","url_pdf":"https://arxiv.org/pdf/2607.07595v1","authors":"[\"Amir Nikabadi\",\"Paweł Rzążewski\"]","published":"2026-07-08T16:13:54Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"cs.DM\",\"cs.DS\"]","methods":"[]","has_code":false}