POLYNOMIAL ALGORITHMS FOR HAMILTONIAN CYCLE IN COCOMPARABILITY GRAPHS

Finding a Hamiltonian cycle in a graph is one of the classical NP-comp lete problems. Complexity of the Hamiltonian problem in permutation gr aphs has been a well-known open problem. In this paper the authors set tle the complexity of the Hamiltonian problem in the more general clas s of cocomparability graphs. It is shown that the Hamiltonian cycle ex istence problem for cocomparability graphs is in P. A polynomial time algorithm for constructing a Hamiltonian path and cycle is also presen ted. The approach is based on exploiting the relationship between the Hamiltonian problem in a cocomparability graph and the bump number pro blem in a partial order corresponding to the transitive orientation of its complementary graph.