Dichotomies for Tree Minor Containment with Structural Parameters
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912144067395584 |
|---|---|
| author | Gima, Tatsuya Kumabe, Soh Kurita, Kazuhiro Okada, Yuto Otachi, Yota |
| author_facet | Gima, Tatsuya Kumabe, Soh Kurita, Kazuhiro Okada, Yuto Otachi, Yota |
| contents | 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 it is NP-complete when $G$ and $H$ are general graphs, it is sometimes tractable on more 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 dichotomies for the computational complexities of the problem based on three structural parameters: the diameter, pathwidth, and path eccentricity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_03225 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Dichotomies for Tree Minor Containment with Structural Parameters Gima, Tatsuya Kumabe, Soh Kurita, Kazuhiro Okada, Yuto Otachi, Yota Data Structures and Algorithms 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 it is NP-complete when $G$ and $H$ are general graphs, it is sometimes tractable on more 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 dichotomies for the computational complexities of the problem based on three structural parameters: the diameter, pathwidth, and path eccentricity. |
| title | Dichotomies for Tree Minor Containment with Structural Parameters |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2311.03225 |