2025/09/07 by Esmer, Barış Can, Marx, Dániel
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2509.06091
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 K3-Packing problem can be solved in time 2tw ⋅ nO(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⋅ 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 2^o(twlog tw)⋅ nO(1) algorithm for H-Partition, assuming the Exponential-Time Hypothesis (ETH).