@InProceedings{AKKT17,
  author =       {V. Arvind and Johannes Köbler and Sebastian Kuhnert
                  and Jacobo Torán},
  title =        {Parameterized complexity of small weight automorphisms},
  year =         2017,
  booktitle =    {Proc. 34th STACS},
  series =       {LIPIcs},
  number =       66,
  publisher =    {Leibniz-Zentrum für Informatik},
  address =      {Dagstuhl},
  isbn =         {978-3-95977-028-6},
  pages =        {7:1-7:13},
  doi =          {10.4230/LIPIcs.STACS.2017.7},
}

Parameterized complexity of small weight automorphisms.
With V. Arvind, Johannes Köbler, Jacobo Torán.
Proceedings of 34th STACS. LIPIcs 66, 2017.

Abstract.

We show that checking if a given hypergraph has an automorphism that moves exactly k vertices is fixed parameter tractable, using k and additionally either the maximum hyperedge size or the maximum color class size as parameters. In particular, it suffices to use k as parameter if the hyperedge size is at most polylogarithmic in the size of the given hypergraph.
As a building block for our algorithms, we generalize Schweitzer’s FPT algorithm [ESA 2011] that, given two graphs on the same vertex set and a parameter k, decides whether there is an isomorphism between the two graphs that moves at most k vertices. We extend this result to hypergraphs, using the maximum hyperedge size as a second parameter.
Another key component of our algorithm is an orbit-shrinking technique that preserves permutations that move few points and that may be of independent interest. Applying it to a suitable subgroup of the automorphism group allows us to switch from bounded hyperedge size to bounded color classes in the exactly-k case.