Hamiltonian cycle is polynomial on cocomparability graphs

Finding a Hamiltonian path or a Hamiltonian cycle in a general graph are classic NP-complete problems. In this paper the authors announce polynomial time solutions for these problems on cocomparability graphs. The present approach is based on exploiting the relationship between the Hamiltonian problem in a cocomparability graph G and the bump number problem in a partial order, the comparability graph of which is the complement of G.