A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles I: Treewidth, Pathwidth, and Grid Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911029911355392 |
|---|---|
| author | Beisegel, Jesse Klost, Katharina Knorr, Kristin Ratajczak, Fabienne Scheffler, Robert |
| author_facet | Beisegel, Jesse Klost, Katharina Knorr, Kristin Ratajczak, Fabienne Scheffler, Robert |
| contents | We consider the problem of finding a Hamiltonian path or a Hamiltonian cycle with precedence constraints in the form of a partial order on the vertex set. We show that the path problem is $\mathsf{NP}$-complete for graphs of pathwidth 4 while the cycle problem is $\mathsf{NP}$-complete on graphs of pathwidth 5. We complement these results by giving polynomial-time algorithms for graphs of pathwidth 3 and treewidth 2 for Hamiltonian paths as well as pathwidth 4 and treewidth 3 for Hamiltonian cycles. Furthermore, we study the complexity of the path and cycle problems on rectangular grid graphs of bounded height. For these, we show that the path and cycle problems are $\mathsf{NP}$-complete when the height of the grid is greater or equal to 7 and 9, respectively. In the variant where we look for minimum edge-weighted Hamiltonian paths and cycles, the problems are $\mathsf{NP}$-hard for heights 5 and 6, respectively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_23790 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles I: Treewidth, Pathwidth, and Grid Graphs Beisegel, Jesse Klost, Katharina Knorr, Kristin Ratajczak, Fabienne Scheffler, Robert Discrete Mathematics Computational Complexity Data Structures and Algorithms Combinatorics We consider the problem of finding a Hamiltonian path or a Hamiltonian cycle with precedence constraints in the form of a partial order on the vertex set. We show that the path problem is $\mathsf{NP}$-complete for graphs of pathwidth 4 while the cycle problem is $\mathsf{NP}$-complete on graphs of pathwidth 5. We complement these results by giving polynomial-time algorithms for graphs of pathwidth 3 and treewidth 2 for Hamiltonian paths as well as pathwidth 4 and treewidth 3 for Hamiltonian cycles. Furthermore, we study the complexity of the path and cycle problems on rectangular grid graphs of bounded height. For these, we show that the path and cycle problems are $\mathsf{NP}$-complete when the height of the grid is greater or equal to 7 and 9, respectively. In the variant where we look for minimum edge-weighted Hamiltonian paths and cycles, the problems are $\mathsf{NP}$-hard for heights 5 and 6, respectively. |
| title | A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles I: Treewidth, Pathwidth, and Grid Graphs |
| topic | Discrete Mathematics Computational Complexity Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2506.23790 |