A Graph Width Perspective on Partially Ordered Hamiltonian Paths
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910859666653184 |
|---|---|
| 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 with precedence constraints in the form of a partial order on the vertex set. This problem is known as Partially Ordered Hamiltonian Path Problem (POHPP). Here, we study the complexity for graph width parameters for which the ordinary Hamiltonian Path problem is in $\mathsf{FPT}$. We show that POHPP is $\mathsf{NP}$-complete for graphs of pathwidth 4. We complement this result by giving polynomial-time algorithms for graphs of pathwidth 3 and treewidth 2. Furthermore, we show that POHPP is $\mathsf{NP}$-hard for graphs of clique cover number 2 and $\mathsf{W[1]}$-hard for some distance-to-$\mathcal{G}$ parameters, including distance to path and distance to clique. In addition, we present $\mathsf{XP}$ and $\mathsf{FPT}$ algorithms for parameters such as distance to block and feedback edge set number. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_03553 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Graph Width Perspective on Partially Ordered Hamiltonian Paths 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 with precedence constraints in the form of a partial order on the vertex set. This problem is known as Partially Ordered Hamiltonian Path Problem (POHPP). Here, we study the complexity for graph width parameters for which the ordinary Hamiltonian Path problem is in $\mathsf{FPT}$. We show that POHPP is $\mathsf{NP}$-complete for graphs of pathwidth 4. We complement this result by giving polynomial-time algorithms for graphs of pathwidth 3 and treewidth 2. Furthermore, we show that POHPP is $\mathsf{NP}$-hard for graphs of clique cover number 2 and $\mathsf{W[1]}$-hard for some distance-to-$\mathcal{G}$ parameters, including distance to path and distance to clique. In addition, we present $\mathsf{XP}$ and $\mathsf{FPT}$ algorithms for parameters such as distance to block and feedback edge set number. |
| title | A Graph Width Perspective on Partially Ordered Hamiltonian Paths |
| topic | Discrete Mathematics Computational Complexity Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2503.03553 |