, Volume 8, Issue 4, pp 383-391

Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm

368 Downloads 200 Citations 9 Comments

Abstract

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 theHamiltonian 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 theHamiltonian Path/Cycle Completion problems in cocomparability graphs.

Communicated by R. H. Möhring
This research was supported in part by ONR for third author and by NSERC under grant number A1798 for fourth author.