ISOMORPHISM TESTING FOR GRAPHS EXCLUDING SMALL MINORS

被引：1

作者：

Grohe, M. A. R. T. I. N. ^{[1
]}

Neuen, D. A. N. I. E. L. ^{[2
]}

Wiebking, D. A. N. I. E. L. ^{[1
]}

机构：

[1] Rhein Westfal TH Aachen, Aachen, Germany

[2] Simon Fraser Univ, Burnaby, BC V5A 1S6, Canada

来源：

SIAM JOURNAL ON COMPUTING | 2023年 / 52卷 / 01期

关键词：

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

D O I：

10.1137/21M1401930

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We prove that there is a graph isomorphism test running in time npolylog(h) on n-vertex graphs excluding some h-vertex graph as a minor. Previously known bounds were npoly(h) [I. N. Ponomarenko, J. Soviet Math., 55 (1991), pp. 1621--1643] and npolylog(n) [L. Babai, Proceedings of the 48th Annual ACM Symposium on Theory of Computing, 2016, pp. 684--697]. For the algorithm we combine recent advances in the group-theoretic graph isomorphism machinery with new graph -theoretic arguments.

引用

页码：238 / 272

页数：35

共 38 条

[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, DOI DOI 10.1017/CBO9780511662157.003
[4] Babai L., 1983, P 15 ANN ACM S THEOR, P171
[5] 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
[6] 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
[7] 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
[8] Chen G., 2019, LECT COHERENT CONFIG
[9] Dixon J.D., 1996, Permutation Groups, V163, DOI DOI 10.1007/978-1-4612-0731-3
[10] Filotti I. S., 1980, P 12 ANN ACM S THEOR, P236

← 1 2 3 4 →