Skip to main content
2 of 4
added first para
domotorp
  • 19.1k
  • 3
  • 59
  • 128

This problem was proved to be NP-complete in https://link.springer.com/article/10.1007/BF00340774, but a mistake was discovered and corrected in https://link.springer.com/article/10.1007%2FBF01108825.

I've asked the same question myself earlier this year from some people working in the field, the above links were given to me by Piotr Micek. Some papers to read are also given in https://arxiv.org/pdf/1908.08250.pdf on page 2, before Theorem 1. Also see https://link.springer.com/article/10.1007/BF00400288.

domotorp
  • 19.1k
  • 3
  • 59
  • 128