Isomorphism Testing for Graphs Excluding Small Minors

被引：6

作者：

Grohe, Martin ^{[1
]}

Wiebking, Daniel ^{[1
]}

Neuen, Daniel ^{[2
]}

机构：

[1] Rhein Westfal TH Aachen, Aachen, Germany

[2] CISPA Helmholtz Ctr Informat Secur, Saarbrucken, Germany

来源：

2020 IEEE 61ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2020) | 2020年

关键词：

graph isomorphism problem; excluded minors; structure of automorphism group; BOUNDED VALENCE; NUMBER;

D O I：

10.1109/FOCS46700.2020.00064

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We prove that there is a graph isomorphism test running in time n(polylog(h)) on n-vertex graphs excluding some h-vertex graph as a minor. Previously known bounds were n(poly(h)) (Ponomarenko, 1988) and n(polylog(n)) (Babai, STOC 2016). For the algorithm we combine recent advances in the group-theoretic graph isomorphism machinery with new graph-theoretic arguments.

引用

页码：625 / 636

页数：12

共 33 条

[1] Babai L., 1983, 24th Annual Symposium on Foundations of Computer Science, P162, DOI 10.1109/SFCS.1983.10
[2] ON THE ORDERS OF PRIMITIVE GROUPS WITH RESTRICTED NON-ABELIAN COMPOSITION FACTORS
BABAI, L
CAMERON, PJ
PALFY, PP
[J]. JOURNAL OF ALGEBRA, 1982, 79 (01) : 161 - 168
[3] BABAI L., 1981, LONDON MATH SOC LECT, V52, P1
[4] Graph Isomorphism in Quasipolynomial Time [Extended Abstract]
Babai, Laszlo
[J]. STOC'16: PROCEEDINGS OF THE 48TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2016, : 684 - 697
[5] Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
Berkholz, Christoph
Bonsma, Paul
Grohe, Martin
[J]. THEORY OF COMPUTING SYSTEMS, 2017, 60 (04) : 581 - 614
[6] AN OPTIMAL LOWER BOUND ON THE NUMBER OF VARIABLES FOR GRAPH IDENTIFICATION
CAI, JY
FURER, M
IMMERMAN, N
[J]. COMBINATORICA, 1992, 12 (04) : 389 - 410
[7] Dixon J.D., 1996, Graduate Texts in Mathematics
[8] Filotti I.S, 1980, STOC
[9] Grohe M, 2020, ABS200407671 CORR
[10] An Improved Isomorphism Test for Bounded-tree-width Graphs
Grohe, Martin
Neuen, Daniel
Schweitzer, Pascal
Wiebking, Daniel
[J]. ACM TRANSACTIONS ON ALGORITHMS, 2020, 16 (03)

← 1 2 3 4 →