NP-completeness properties about linear extensions (Q581427): Difference between revisions

The authors present ``some complexity results about the construction of depth-first greedy linear extensions''. They prove ``that the recognition of Dilworth partially ordered sets of height 2, as defined by Sysło, is NP-complete. This last result yields a new proof of the NP-completeness of the jump number problem, first proved by Pulleyblank''. The following theorems are presented: Theorem 1. Not depth-first greedy is NP-complete. Theorem 2. Weakly depth-first greedy is NP-hard. Theorem 3. Recognition of Dilworth posets is NP-complete. Corollary. The jump number is NP-hard.