NP-completeness results concerning greedy and super greedy linear extensions (Q1087567)

The problem of determining that an ordered set is not greedy is NP- complete. Let \({\mathcal P}=(P,\leq)\) be an ordered set and \({\mathcal P}'\) a partial extension of \({\mathcal P}\). The problem of determining that there exists a (super) greedy linear extension of \({\mathcal P}\) which is also an extension of \({\mathcal P}'\) is NP-complete.