License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.88
URN: urn:nbn:de:0030-drops-124959
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12495/
Go to the corresponding LIPIcs Volume Portal

Neuen, Daniel

Hypergraph Isomorphism for Groups with Restricted Composition Factors

pdf-format:
LIPIcs-ICALP-2020-88.pdf (0.5 MB)

Abstract

We consider the isomorphism problem for hypergraphs taking as input two hypergraphs over the same set of vertices V and a permutation group Γ over domain V, and asking whether there is a permutation γ ∈ Γ that proves the two hypergraphs to be isomorphic. We show that for input groups, all of whose composition factors are isomorphic to a subgroup of the symmetric group on d points, this problem can be solved in time (n+m)^O((log d)^c) for some absolute constant c where n denotes the number of vertices and m the number of hyperedges. In particular, this gives the currently fastest isomorphism test for hypergraphs in general. The previous best algorithm for the above problem due to Schweitzer and Wiebking (STOC 2019) runs in time n^O(d)m^O(1).
As an application of this result, we obtain, for example, an algorithm testing isomorphism of graphs excluding K_{3,h} as a minor in time n^O((log h)^c). In particular, this gives an isomorphism test for graphs of Euler genus at most g running in time n^O((log g)^c).

BibTeX - Entry

@InProceedings{neuen:LIPIcs:2020:12495,
  author =	{Daniel Neuen},
  title =	{{Hypergraph Isomorphism for Groups with Restricted Composition Factors}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{88:1--88:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Artur Czumaj and Anuj Dawar and Emanuela Merelli},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12495},
  URN =		{urn:nbn:de:0030-drops-124959},
  doi =		{10.4230/LIPIcs.ICALP.2020.88},
  annote =	{Keywords: graph isomorphism, groups with restricted composition factors, hypergraphs, bounded genus graphs}
}

Keywords: graph isomorphism, groups with restricted composition factors, hypergraphs, bounded genus graphs
Collection: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Issue Date: 2020
Date of publication: 29.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI