2026-07-22T13:27:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24471 2025-12-16T13:59:32Z ddc:004 open_access

Generalized Graph Packing Problems Parameterized by Treewidth Can Esmer, Barış Marx, Dániel Graph Packing Graph Partitioning Parameterized Complexity Treewidth Pathwidth pw-SETH Single-Exponential Lower Bound Slightly Superexponential Lower Bound 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 K_d 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 K_d 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 log tw)⋅ n^O(1) algorithm for H-Partition, assuming the Exponential-Time Hypothesis (ETH). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Barış Can Esmer and Dániel Marx 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.3 urn:nbn:de:0030-drops-244713 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.3 eng https://creativecommons.org/licenses/by/4.0/legalcode