*BibTeX*

@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

kvertices is fixed parameter tractable, usingkand additionally either the maximum hyperedge size or the maximum color class size as parameters. In particular, it suffices to usekas 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 parameterk, decides whether there is an isomorphism between the two graphs that moves at mostkvertices. 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-kcase.