The Fixed Point Property for Ordered Sets of Interval Dimension 2

We provide a polynomial time algorithm that identifies if a given finite ordered set is in the class of d2-collapsible ordered sets. For a d2-collapsible ordered set, the algorithm also determines if the ordered set is connectedly collapsible. Because finite ordered sets of interval dimension 2 are d2-collapsible, in particular, the algorithm determines in polynomial time if a given finite ordered set of interval dimension 2 has the fixed point property. This result is also a first step in investigating the complexity status of the question whether a given collapsible ordered set has the fixed point property.