Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-157 | 13th October 2016 15:42

Parameterized Complexity of Small Weight Automorphisms

RSS-Feed




TR16-157
Authors: Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Toran
Publication: 17th October 2016 15:46
Downloads: 991
Keywords: 


Abstract:

We consider the PermCode problem to decide, given a representation of a permutation group G and a parameter k, whether there is a non-trivial element of G with support at most k. This problem generalizes several problems in the literature. We introduce a new method that allows to reduce the maximal orbit size of the group being considered while maintaining elements with small support in the group. Using this technique we provide upper and lower bounds for several variants of the parameterized Hypergraph Isomorphism Problem that extend previous results on parameterized Graph Isomorphism.



ISSN 1433-8092 | Imprint