文章基本信息

标题：Parameterized Complexity of Small Weight Automorphisms
本地全文：下载
作者：Vikraman Arvind ; Johannes Köbler ; Sebastian Kuhnert 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2016
卷号：2016
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
关键词：Hypergraph Isomorphism ; Parameterized Complexity