Computing the jump number on semi-orders is polynomial

AbstractSemi-orders form a subclass of interval orders: they can be represented as sets of intervals of a given length. We first prove that semi-orders can be partitioned by serialization (or series decomposition) without loss of the jump number aspect. On non-serializable semi-orders all linear extensions contain never more than two consecutive bumps (maximal chains of length at most 3). We then give a “divide-and-conquer” argument proving that to solve this case all we need is to be able to compute the number of maximal chains of length at least 2. This can also be dealt with in polynomial time, allowing us to claim that computing the jump number is polynomial on semi-orders