{"ID":2873795,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.06091","arxiv_id":"2509.06091","title":"Generalized Graph Packing Problems Parameterized by Treewidth","abstract":"$H$-Packing is the problem of finding a maximum number of vertex-disjoint copies of $H$ in a given graph $G$. $H$-Partition is the special case of finding a set of vertex-disjoint copies that cover each vertex of $G$ exactly once. Our goal is to study these problems and some generalizations on bounded-treewidth graphs. The case of $H$ being a triangle is well understood: given a tree decomposition of $G$ having treewidth $tw$, the $K_3$-Packing problem can be solved in time $2^{tw} \\cdot n^{O(1)}$, while Lokshtanov et al.~[{\\it ACM Transactions on Algorithms} 2018] showed, under the Strong Exponential-Time Hypothesis (SETH), that there is no $(2-ε)^{tw}\\cdot n^{O(1)}$ algorithm for any $ε\u003e0$ even for $K_3$-Partition. Similar results can be obtained for any other clique $K_d$ for $d\\ge 3$. We provide generalizations in two directions: - We consider a generalization of the problem where every vertex can be used at most $c$ times for some $c\\ge 1$. When $H$ is any clique $K_d$ with $d\\ge 3$, then we give upper and lower bounds showing that the optimal running time increases to $(c+1)^{tw}\\cdot n^{O(1)}$. We consider two variants depending on whether a copy of $H$ can be used multiple times in the packing. - If $H$ is not a clique, then the dependence of the running time on treewidth may not be even single exponential. Specifically, we show that if $H$ is any fixed graph where not every 2-connected component is a clique, then there is no $2^{o({tw}\\log {tw})}\\cdot n^{O(1)}$ algorithm for \\textsc{$H$-Partition}, assuming the Exponential-Time Hypothesis (ETH).","short_abstract":"$H$-Packing is the problem of finding a maximum number of vertex-disjoint copies of $H$ in a given graph $G$. $H$-Partition is the special case of finding a set of vertex-disjoint copies that cover each vertex of $G$ exactly once. Our goal is to study these problems and some generalizations on bounded-treewidth graphs....","url_abs":"https://arxiv.org/abs/2509.06091","url_pdf":"https://arxiv.org/pdf/2509.06091v1","authors":"[\"Barış Can Esmer\",\"Dániel Marx\"]","published":"2025-09-07T15:14:51Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\"]","methods":"[]","has_code":false}