文章基本信息

标题：Parameterized Complexity of Small Weight Automorphisms
本地全文：下载
作者：Vikraman Arvind ; Johannes K{\"o}bler ; Sebastian Kuhnert 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：66
页码：7:1-7:13
DOI：10.4230/LIPIcs.STACS.2017.7
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Parameterized algorithms; hypergraph isomorphism.