2025/06/30 by Jesse Beisegel, Beisegel, Jesse, Katharina Klost +7 · 2 citations
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.2506.23790
openalex publication_date 2025/06/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 NP-complete for graphs of pathwidth 4 while the cycle problem is 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 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 NP-hard for heights 5 and 6, respectively.