next up previous contents index
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.,

  define3596

define3606

  theorem3611

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:

define3617

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 tex2html_wrap_inline8314 via the order tex2html_wrap_inline7824 defined as follows:

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

displaymath8350

and

displaymath8352

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.

   figure3632
Figure 2: The ordered set used in the second proof of Theorem 2.14: Consider an instance of 3SAT with m distinct clauses tex2html_wrap_inline7782 , each of which contains exactly 3 distinct literals tex2html_wrap_inline7784 out of tex2html_wrap_inline8462 . The satisfiabiliy component is an antichain of points tex2html_wrap_inline7788 , 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 tex2html_wrap_inline7788 are tex2html_wrap_inline7796 and tex2html_wrap_inline7798 .

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 tex2html_wrap_inline8480 each of which has 3 distinct literals tex2html_wrap_inline7784 out of tex2html_wrap_inline8462 we construct the ordered set P as indicated in Figure 2. Note that each tex2html_wrap_inline7788 has a unique set of 6 upper covers. For tex2html_wrap_inline8494 , let tex2html_wrap_inline8496 . Then it is easy to see that every automorphism of P must fix the satisfiability component and every tex2html_wrap_inline8500 . Each tex2html_wrap_inline8500 has exactly four fixed point free automorphisms, of which only tex2html_wrap_inline8504 and tex2html_wrap_inline8506 (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 tex2html_wrap_inline8514 is a fixed point free automorphism. If tex2html_wrap_inline8516 , set tex2html_wrap_inline8518 TRUE. Otherwise we have tex2html_wrap_inline8520 , and we set tex2html_wrap_inline8518 FALSE. Now if tex2html_wrap_inline8524 and tex2html_wrap_inline8526 were all false for some j, then the definitions of tex2html_wrap_inline8530 and tex2html_wrap_inline8532 indicate that tex2html_wrap_inline8534 must interchange tex2html_wrap_inline8536 and tex2html_wrap_inline8538 , tex2html_wrap_inline8540 and tex2html_wrap_inline8542 , and tex2html_wrap_inline8544 and tex2html_wrap_inline8546 . Since these are the upper covers of tex2html_wrap_inline8548 we conclude that tex2html_wrap_inline8548 is a fixed point of tex2html_wrap_inline8534 , a contradiction.
On the other hand if tex2html_wrap_inline8554 is a satisfying assignment for C (with 0 standing for FALSE and 1 standing for TRUE as usual), we define tex2html_wrap_inline8534 as follows: Set tex2html_wrap_inline8564 if tex2html_wrap_inline8518 is true (1), set tex2html_wrap_inline8570 if tex2html_wrap_inline8518 is false (0) and set tex2html_wrap_inline8576 , where tex2html_wrap_inline8578 denotes addition modulo 2. Since one of tex2html_wrap_inline7784 is 1 (true), tex2html_wrap_inline8534 has no fixed points. tex2html_wrap_inline8534 trivially is an automorphism on the truth setting component. Since addition of a 1 or a 0 modulo 2 is injective, tex2html_wrap_inline8534 is injective and hence bijective on the satisfiability component. Finally one checks that tex2html_wrap_inline8534 is order-preserving. \

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

define3782

cor3786

Proof: If there was an algorithm that decides if a given r-partite graph G=(V,E) with partition tex2html_wrap_inline8628 and tex2html_wrap_inline8630 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).\

cor3790

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


next up previous contents index
Next: Xia's Reduction Algorithm Up: Complexity Previous: Endomorphism Graphs

Bernd.S.W.Schroder