An Optimal Algorithm to Find the Jump Number of Partially Ordered Sets

The jump number of a partially ordered set (poset) P is the minimum number of incomparable adjacent pairs (jumps) in some linear extension of P. The problem of finding a linear extension of P with minimum number of jumps (jump number problem) is known to be NP-hard in general and, at the best of our knowledge, no exact algorithm for general posets has been developed. In this paper, we give examples of applications of this problem and propose for the general case a new heuristic algorithm and an exact algorithm. Performances of both algorithms are experimentally evaluated on a set of randomly generated test problems.