2026-07-26T21:31:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7027 2024-03-06T10:39:08Z ddc:004 open_access

Parameterized Complexity of Small Weight Automorphisms Arvind, Vikraman Köbler, Johannes Kuhnert, Sebastian Torán, Jacobo Parameterized algorithms hypergraph isomorphism. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vikraman Arvind and Johannes Köbler and Sebastian Kuhnert and Jacobo Torán 2017 Is Part Of LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2017.7 urn:nbn:de:0030-drops-70278 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.7 eng https://creativecommons.org/licenses/by/3.0/legalcode