Minimizing bumps in linear extensions of ordered sets (Q1077441)

Given a finite partially ordered set P, there are many ways of imbedding the set into a linearly ordered one respecting order. Whenever \(a<b\), but a is incomparable to b in the original order, one speaks of a ''jump''. Up to the present there is no known efficient algorithm to linearly extend a poset, minimizing the number of jumps. It seems to be known that determining the so-called ''jump number'', i.e. the minimal number of jumps that must occur in any linearization, is NP-complete [W. R. Pulleyblank (to appear)]. The paper under review takes the opposite point of view by calling a ''bump'' an occurrence of \(a<b\), with \(a<b\) also in the original order. The problem is now to minimize bumps, which is equivalent to maximize jumps. (The puns involved in this choice of words are unfortunate, as they could never be translated into another language.) The authors study some possible algorithms for this problem. As in the case of the first problem, there are always some sufficient conditions on posets to guarantee optimality, but no necessary ones seem to be known.