Dichotomies for tree minor containment with structural parameters

The problem of determining whether a graph G contains another graph H as a minor, referred to as the minor containment problem, is a fundamental problem in the field of graph algorithms. While the problem is NP -complete in general, it can be tractable on some restricted graph classes. This study focuses on the case where both G and H are trees, known as the tree minor containment problem. Even in this case, the problem is known to be NP -complete. In contrast, polynomial-time algorithms are known for the case when both trees are caterpillars or when the maximum degree of H is a constant. Our research aims to clarify the boundary of tractability and intractability for the tree minor containment problem. Specifically, we provide complexity dichotomies for the problem based on three structural parameters: diameter, pathwidth, and path eccentricity.

Authors

• Tatsuya Gima
• Soh Kumabe
• Kazuhiro Kurita
• Yuto Okada
• Yota Otachi Nagoya University

Keywords

• Minor containment
• Tree
• Diameter
• Path eccentricity
• Pathwidth