Computing Hamiltonian Paths with Partial Order Restrictions
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913708808077312 |
|---|---|
| author | Beisegel, Jesse Ratajczak, Fabienne Scheffler, Robert |
| author_facet | Beisegel, Jesse Ratajczak, Fabienne Scheffler, Robert |
| contents | When solving the Hamiltonian path problem it seems natural to be given additional precedence constraints for the order in which the vertices are visited. For example one could decide whether a Hamiltonian path exists for a fixed starting point, or that some vertices are visited before another vertex. We consider the problem of finding a Hamiltonian path that observes all precedence constraints given in a partial order on the vertex set. We show that this problem is $\mathsf{NP}$-complete even if restricted to complete bipartite graphs and posets of height 2. In contrast, for posets of width $k$ there is a known $\mathcal{O}(k^2 n^k)$ algorithm for arbitrary graphs with $n$ vertices. We show that it is unlikely that the running time of this algorithm can be improved significantly, i.e., there is no $f(k) n^{o(k)}$ time algorithm under the assumption of the Exponential Time Hypothesis. Furthermore, for the class of outerplanar graphs, we give an $\mathcal{O}(n^2)$ algorithm for arbitrary posets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_16662 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computing Hamiltonian Paths with Partial Order Restrictions Beisegel, Jesse Ratajczak, Fabienne Scheffler, Robert Discrete Mathematics Computational Complexity Data Structures and Algorithms Combinatorics When solving the Hamiltonian path problem it seems natural to be given additional precedence constraints for the order in which the vertices are visited. For example one could decide whether a Hamiltonian path exists for a fixed starting point, or that some vertices are visited before another vertex. We consider the problem of finding a Hamiltonian path that observes all precedence constraints given in a partial order on the vertex set. We show that this problem is $\mathsf{NP}$-complete even if restricted to complete bipartite graphs and posets of height 2. In contrast, for posets of width $k$ there is a known $\mathcal{O}(k^2 n^k)$ algorithm for arbitrary graphs with $n$ vertices. We show that it is unlikely that the running time of this algorithm can be improved significantly, i.e., there is no $f(k) n^{o(k)}$ time algorithm under the assumption of the Exponential Time Hypothesis. Furthermore, for the class of outerplanar graphs, we give an $\mathcal{O}(n^2)$ algorithm for arbitrary posets. |
| title | Computing Hamiltonian Paths with Partial Order Restrictions |
| topic | Discrete Mathematics Computational Complexity Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2404.16662 |