Next: Xia's Reduction Algorithm Up: Complexity Previous: Endomorphism Graphs

Fixed Point Free Automorphisms

The problem of deciding whether a finite ordered set has a fixed point free automorphism was found by Williamson to be NP-complete (cf. [132], Fact 5.1 or Theorem 2.14 here), i.e.,

We will present two proofs of this theorem here. One by Goddard that reduces the problem to a known NP-complete problem, namely the determination if a given graph has a fixed point free automorphism (cf. [79]). The other is Williamson's original adaptation of Lubiw's proof in [79], which reduces the problem to 3SAT. This proof will be sketched only. For the first proof we need:

Proof 1 of Theorem 2.14: (T. Goddard, private communication, also cf. [29]) By [79] it is NP-complete to decide if a given graph has a fixed point free automorphism. We will show that any algorithm that decides if an arbitrary ordered set P has a fixed point free automorphism in q(|P|) steps also decides if an arbitrary graph G=(V,E) has a fixed point free automorphism in q'(|V|) steps, where q,q' are polynomials.
Let G=(V,E) be a graph. Order the set via the order defined as follows:

1. is reflexive,
2. No two vertices of G are related,
3. No two elements of are related,
4. If and , then v<(e,x) iff .
Clearly |P| is bounded by a polynomial function of |V|. Moreover P has a fixed point free automorphism iff G does: If is a fixed point free automorphism, then is a fixed point free automorphism of G. Conversely, if is a fixed point free automorphism of G, then let

and

f is a fixed point free automorphism of P. \

Thus we even know that the problem to decide if an ordered set of height 1 has a fixed point free automorphism is NP-complete (this is also noted as Fact 5.2 in [132]). This is interesting in the light of Theorem 3.21 and Corollary 3.24, which show that there is an efficient algorithm to detect if an ordered set of height 1 has a fixed point free order-preserving self map. Our second proof is a reduction to 3SAT itself.

Figure 2: The ordered set used in the second proof of Theorem 2.14: Consider an instance of 3SAT with m distinct clauses , each of which contains exactly 3 distinct literals out of . The satisfiabiliy component is an antichain of points , where abc counts from zero to 7 in binary. The truth setting component has comparabilities as indicated. Finally (not indicated in the figure) the upper covers of are and .

Proof 2 of Theorem 2.14: (cf. [132], Fact 5.1; we present a sketch) For a given instance C of 3SAT which we can without loss of generality choose to have m distinct clauses each of which has 3 distinct literals out of we construct the ordered set P as indicated in Figure 2. Note that each has a unique set of 6 upper covers. For , let . Then it is easy to see that every automorphism of P must fix the satisfiability component and every . Each has exactly four fixed point free automorphisms, of which only and (we remain consistent with the notation in [132] here) can possibly extend to an automorphism of P (the other two map sets that have a lower bound in the satisfiability component to sets that do not have lower bounds).
To show that P has a fixed point free automorphism iff there is a satisfying assignment for C first assume that is a fixed point free automorphism. If , set TRUE. Otherwise we have , and we set FALSE. Now if and were all false for some j, then the definitions of and indicate that must interchange and , and , and and . Since these are the upper covers of we conclude that is a fixed point of , a contradiction.
On the other hand if is a satisfying assignment for C (with 0 standing for FALSE and 1 standing for TRUE as usual), we define as follows: Set if is true (1), set if is false (0) and set , where denotes addition modulo 2. Since one of is 1 (true), has no fixed points. trivially is an automorphism on the truth setting component. Since addition of a 1 or a 0 modulo 2 is injective, is injective and hence bijective on the satisfiability component. Finally one checks that is order-preserving. \

Using the characterization in Remark 2.11 we can also record some known results as easy consequences:

Proof: If there was an algorithm that decides if a given r-partite graph G=(V,E) with partition and contains an r-clique in q(|V|) steps, then by Remark 2.11 there would be an algorithm that determines if the fixed point free automorphism graph of a given ordered set P has a |P|-clique in q'(|P|) steps. Thus we could determine if a given ordered set P has a fixed point free automorphism in q''(|P|) steps (q,q',q'' all polynomials).\

Proof: If there was an algorithm that determines if a given graph G=(V,E) with has an r-clique in q(|V|) steps, then this algorithm would decide if a given r-partite graph G=(V,E) with partition and has an r-clique in q(|V|) steps. \

Next: Xia's Reduction Algorithm Up: Complexity Previous: Endomorphism Graphs

Bernd.S.W.Schroder