On the complexity of list $\mathcal{H}$-packing for sparse graph classes

Abstract

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.