The jump number of Z-free ordered sets (Q1183946)

Let \(P\) be a finite poset and \(L\) a linear extension of \(P\). A consecutive pair \((x,y)\) in \(L\) is a jump if \(x\) and \(y\) are not comparable in \(P\). If \(s(P,L)\) denotes the number of jumps in \(L\) then the jump number of \(P\) is defined by \(s(P)=\min\{s(P,L)\mid L\) a linear extension of \(P\}\). The jump number problem is to find \(s(P)\) and to construct an optimal linear extension of \(P\). It is known that this problem has practical applications to scheduling or sorting and it is NP- hard. However, polynomial-time algorithms are known for several classes of posets generally obtained by forbidding certain suborder configurations of a poset. An ordered set is called \(Z\)-free if it does not contain a 4-element subset \(\{a,b,c,d\}\) in which \(a<b\) and \(c<b\) are the only comparabilities. In this paper seven lemmas and two theorems are proved to derive a polynomial-time algorithm which solves the jump problem for \(Z\)-free ordered sets (and their order-duals). In fact, starting from an idea of the author and \textit{N. Zaguia} [Order 7, 353-359 (1991; Zbl 0735.06002)], it is shown that for any finite \(Z\)-free ordered set \(P\), we can always find in polynomial time a subset \(Q\subseteq P\) for which \(s(P-Q)=s(P)-1\) or \(s(P-Q)=s(P)\).