The Fixed Point Property for Ordered Sets of Interval Dimension 2
Mathematics and Natural Sciences
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.
Schröder, B. S.
(2017). The Fixed Point Property for Ordered Sets of Interval Dimension 2. Order, 34(2), 307-322.
Available at: https://aquila.usm.edu/fac_pubs/15308