Computing the bump number with techniques from two-processor scheduling (Q1106865)

Let (X,\(\prec)\) be a partially ordered set. A linear extension \(x_ 1,x_ 2,..\). has a bump whenever \(x_ i\prec x_{i+1}\), and it has a jump whenever \(x_ i\) and \(x_{i+1}\) are incomparable. The problem of finding a linear extension that minimizes the number of jumps has been studied extensively; \textit{W. R. Pulleyblank} [On minimizing setups in precedence constrained scheduling (to appear)] shows that it is NP- complete in the general case. \textit{P. C. Fishburn} and \textit{W. V. Gehrlein} [Order 3, 3-14 (1986; Zbl 0595.06004)] raise the question of finding a linear extension that minimizes the number of bumps. We show that the bump number problem is closely related to the well-studied problem of scheduling unit-time tasks with a precedence partial order on two identical processors. We point out that a variant of Gabow's linear- time algorithm for the two-processor scheduling problem solves the bump number problem. The authors of the paper reviewed above (see Zbl 0652.06002) have independently discovered a different polynomial-time algorithm to solve the bump number problem.