Xia's algorithm (cf. [134]),
a variant of which we are about to describe,
terminates in polynomial
time. If it terminates with a graph with no edges, the ordered
set is known to have the fixed point property
(cf. Theorem 2.22).
The main idea is that certain
combinations of elements in cannot be
contained in an order-preserving map
(cf. Lemma 2.19).
Formulating our results in the language of graph theory
it seems that the ``natural habitat" of Xia's algorithm
is the decision if a given *r*-partite
graph *G*=(*V*,*E*) with partition
and
contains an *r*-clique.

**Proof:**
This is obvious, as otherwise would contain a
complete induced subgraph with vertices
(*p*,*q*), (*p*',*q*'), (*b*,*c*)
(a ``triangle") for some (resp.
some ). \

The Lack-of-a-triangle Lemma now suggests the following removal step which is decribed as step II in [134] on p. 260:

Xia's algorithm now iterates this removal step until the iteration is no longer possible.

**Proof:** As *G* is a subgraph of the endomorphism graph of *P*, the
direction `` " is clear.
To prove `` ", we perform an induction on *n*, the
number of iterations of the removal steps.
For *n*=0 the result is true by Corollary 2.9.
Now assume that *G*=(*V*,*E*) has been obtained
from the (fixed point free) endomorphism graph
through
iterations of the removal step and that if
is an order-preserving self map
of *P* then
is a
|*P*|-clique of *G*.
Let be the graph obtained in the
iteration of the removal step and let
be an order-preserving self map.
Then the removed edge cannot be an edge that connects two
elements of . Thus the conclusion holds in .
\

Proposition 2.20
shows that iteration of the removal step
``does not destroy any (fixed point free) self maps".
Thus if this iteration eventually produces a graph
with an empty edge set, then
*P* must have the fixed point property.
Obviously this suggested algorithm is polynomial.
Moreover Proposition 2.21 shows that
the graph obtained by iterating the removal step until
no further edges can be removed is independent of the order in
which edges are removed resp. independent of the search pattern
used in **REMOVE**.

**Proof:**
Part 1 is obvious and part 3 easily
follows from the fact that a finite ordered set
that satisfies 2
and has a largest
element also
has a smallest element
(cf. [39]; Farley's argument in [39] obviously is the
template for this proof).
Thus we are left to prove part 2.
Note that *F* is an upper cover of *F*' in *R* iff
and *F*' is obtained from *F* by applying the
removal step once. Now suppose that *A*,*B* are in *R* and
*U* is an upper cover of *A* and *B*. Let be the edge
such that and let
be such that .
Then the removal step can be applied to *U* to remove *a* or *b*
(whichever is found first) and
hence the removal step can be applied
to *A* to remove *b* (find *b* and remove it) and it can be applied to
*B* to remove *a* (find *a* and remove it). Thus
is a lower cover of *A* and *B* in *R*. \

**Proof:**
By Proposition 2.21
**REMOVE** will eventually lead to a graph with no edges
independent of the specific iteration being used.
By Proposition 2.20
*P* has no fixed point free order-preserving map, since
*G* has no |*P*|-clique. \

At the end of [134] it is proved that Xia's algorithm
terminates with a graph with no edges when *P* is dismantlable
(cf. Example 3.9, part 1).
This is not surprising, as dismantlability can be checked in
polynomial time and implies the fixed point property.
Little is known about for what classes of ordered sets
termination of Xia's algorithm with a graph that has edges
guarantees the existence of a fixed point free self map
(cf. open question 1).
It is easy to show that Xia's algorithm terminates with a graph with
no edges for connectedly collapsible ordered sets
(cf. Definition 4.26)
of height 2 and a modification of the proof in
[37] shows the same is true for
ordered sets with the cutset property.