next up previous contents index
Next: Late-breaking News ... Up: Complexity Previous: Fixed Point Free Automorphisms

Xia's Reduction Algorithm


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 tex2html_wrap_inline8672 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 tex2html_wrap_inline8628 and tex2html_wrap_inline8630 contains an r-clique.


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

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

REMOVE Let G=(V,E) be a subgraph of the   (fixed point free) endomorphism graph. Find an edge tex2html_wrap_inline8718 such that there is a tex2html_wrap_inline8720 such that no tex2html_wrap_inline8722 ( tex2html_wrap_inline8724 ) is adjacent in G to both (p,q) and (p',q'). Remove tex2html_wrap_inline8144 from E to obtain a new graph tex2html_wrap_inline8736 . If this cannot be done, stop.

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 `` tex2html_wrap_inline8148 " is clear. To prove `` tex2html_wrap_inline8128 ", 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 tex2html_wrap_inline8768 iterations of the removal step and that if tex2html_wrap_inline8130 is an order-preserving self map of P then tex2html_wrap_inline8132 is a |P|-clique of G. Let tex2html_wrap_inline8780 be the graph obtained in the tex2html_wrap_inline8782 iteration of the removal step and let tex2html_wrap_inline8130 be an order-preserving self map. Then the removed edge cannot be an edge that connects two elements of tex2html_wrap_inline8132 . Thus the conclusion holds in tex2html_wrap_inline8780 . \

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 tex2html_wrap_inline8820 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 tex2html_wrap_inline8836 be the edge such that tex2html_wrap_inline8838 and let tex2html_wrap_inline8840 be such that tex2html_wrap_inline8842 . 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 tex2html_wrap_inline8862 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.

next up previous contents index
Next: Late-breaking News ... Up: Complexity Previous: Fixed Point Free Automorphisms