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 条

[21] ISOMORPHISM OF GRAPHS OF BOUNDED VALENCE CAN BE TESTED IN POLYNOMIAL-TIME
LUKS, EM
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1982, 25 (01) : 42 - 65
[22] HOMOMORPHISM PROPERTIES AND MEAN EDGE THICKNESS OF GRAPHS
MADER, W
[J]. MATHEMATISCHE ANNALEN, 1967, 174 (04) : 265 - &
[23] Miller G.L., 1980, P 12 ACM S THEOR COM, P225, DOI DOI 10.1145/800141.804670
[24] ISOMORPHISM OF K-CONTRACTIBLE GRAPHS - A GENERALIZATION OF BOUNDED VALENCE AND BOUNDED GENUS
MILLER, GL
[J]. INFORMATION AND CONTROL, 1983, 56 (1-2): : 1 - 20
[25] Neuen D, 2022, PROCEEDINGS OF THE 2022 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, P1411
[26] Hypergraph Isomorphism for Groups with Restricted Composition Factors
Neuen, Daniel
[J]. ACM TRANSACTIONS ON ALGORITHMS, 2022, 18 (03)
[27] Neuen Daniel, 2019, Ph. D. Dissertation, DOI [10.18154/RWTH-2020-00160, DOI 10.18154/RWTH-2020-00160]
[28] Ponomarenko I. N., 1991, J. Soviet Math., V55, P1621, DOI DOI 10.1007/BF01098279
[29] PONOMARENKO IN, 1989, DOKL AKAD NAUK SSSR+, V304, P552
[30] Graph minors. XVI. Excluding a non-planar graph
Robertson, N
Seymour, PD
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2003, 89 (01) : 43 - 76

← 1 2 3 4 →