Computing Hamiltonian Paths with Partial Order Restrictions
<|reference_start|>Computing Hamiltonian Paths with Partial Order Restrictions: 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 an $\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.<|reference_end|>
@article{beisegel2024computing,
    title={Computing Hamiltonian Paths with Partial Order Restrictions},
    author={Jesse Beisegel, Fabienne Ratajczak, and Robert Scheffler},
    journal={arXiv preprint arXiv:2404.16662},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.16662},
    primaryClass={cs.DM cs.CC cs.DS math.CO}
}