Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm (Q1198484)

The cocomparability graph of a partial order is the graph whose edges are the incomparable pairs in the partial order. It is shown that the Hamiltonian Path problem can be solved in polynomial time for cocomparability graphs, and thus for the subclass of permutation graphs. The proof uses results on the bump numbers of partially ordered sets, and relationships between Hamiltonian paths in the cocomparability graphs and the bump numbers. The existence of polynomial time algorithms for path (cycle) completion problems in cocomparability graphs is proved.