Computing fixed point free automorphisms of graphs
This work addresses computational complexity and algorithmic efficiency for graph automorphism problems, with incremental extensions to specific graph classes.
The paper proves that the fixed point free automorphism problem remains NP-complete for several graph classes (split, bipartite, k-subdivided, and H-free graphs where H is not an induced subgraph of P_4), and provides polynomial-time algorithms for three extensions of cographs (bounded modular-width graphs, tree-cographs, and P_4-sparse graphs).
In 1981, Lubiw proved that the fixed point free automorphism problem (FPFAut) is NP-complete: given a graph G, determine whether there exists an automorphism that maps no vertex of G to itself. We revisit this problem and prove that FPFAut remains NP-complete when restricted to split, bipartite, k-subdivided, and H-free graphs, if H is not an induced subgraph of P_4. The class of P_4-free graphs receives the special name of cographs. We provide a polynomial time algorithm for three extensions of cographs: bounded modular-width graphs, tree-cographs and P_4-sparse graphs. Our approach uses the well known modular decomposition of graphs. As a consequence, we generalize a result of Abiad et. al. on the problem of computing 2-homogeneous equitable partitions.