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^tw n^O (1), while Lokshtanov et al. ~ ACM Transactions on Algorithms 2018 showed, under the Strong Exponential-Time Hypothesis (SETH), that there is no (2-ε) ^tw n^O (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) ^tw 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 tw) } n^O (1) algorithm for H-Partition, assuming the Exponential-Time Hypothesis (ETH).
Esmer et al. (Sun,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: