On the Complexity of List \(\mathcal H\) -Packing for Sparse Graph Classes

The problem of packing as many subgraphs isomorphic to \(H \in \mathcal H\) as possible in a graph for a class \(\mathcal H\) of graphs is well studied in the literature. Both vertex-disjoint and edge-disjoint versions are known to be NP-complete for H that contains at least three vertices and at least three edges, respectively. In this paper, we consider “list variants” of these problems: Given a graph G, an integer k, and a collection \(\mathcal L_{\mathcal H}\) of subgraphs of G isomorphic to some \(H \in \mathcal H\) , the goal is to compute k subgraphs in \(\mathcal L_{\mathcal H}\) that are pairwise vertex- or edge-disjoint. We show several positive and negative results, focusing on classes of sparse graphs, such as bounded-degree graphs, planar graphs, and bounded-treewidth graphs.