Back to Search Start Over

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

Authors :
Gima, Tatsuya
Hanaka, Tesshu
Kobayashi, Yasuaki
Otachi, Yota
Shirai, Tomohito
Suzuki, Akira
Tamura, Yuma
Zhou, Xiao
Publication Year :
2023

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.

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2312.08639
Document Type :
Working Paper