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 boundedtreewidth graphs. The case of H being a triangle is well understood: given a tree decomposition of G having treewidth tw, the K3-Packing problem can be solved in time 2tw · nO(1), while Lokshtanov et al. [ACM Transactions on Algorithms 2018] showed, under the Strong Exponential-Time Hypothesis (SETH), that there is no (2 − ϵ)tw · nO(1) algorithm for any ϵ > 0 even for K3-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 · 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 2o(tw log tw)· nO(1) algorithm for H-Partition, assuming the Exponential-Time Hypothesis (ETH)
European Symposium on Algorithms (ESA)
2025
2025-10-23