FINDING HAMILTONIAN PATHS IN COCOMPARABILITY GRAPHS USING THE BUMP NUMBER ALGORITHM

Hamiltonian Path/Cycle are well known NP-complete problems on general graphs, but their complexity status for permutation graphs has been an open question in algorithmic graph theory for many years. In this paper, we prove that the Hamiltonian Path problem is solvable in polynomial time even for the larger class of cocomparability graphs. Our result is based on a nice relationship between Hamiltonian paths and the bump number of partial orders. As another consequence we get a new interpretation of the bump number in terms of path partitions, leading to polynomial time solutions of the Hamiltonian Path/Cycle Completion problems in cocomparability graphs.