Generalized Graph Packing Problems Parameterized by Treewidth

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₃-Packing problem can be solved in time 2ᵗʷ · nO(1), while Lokshtanov et al.~[{ ACM Transactions on Algorithms} 2018] showed, under the Strong Exponential-Time Hypothesis (SETH), that there is no (2-ε)ᵗʷ· nO(1) algorithm for any $ε>0$ even for K₃-Partition. Similar results can be obtained for any other clique Kd for d≥ 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≥ 1. When H is any clique Kd with d≥ 3, then we give upper and lower bounds showing that the optimal running time increases to (c+1)ᵗʷ· nO(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(twlog tw)· nO(1) algorithm for {H-Partition}, assuming the Exponential-Time Hypothesis (ETH).