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 条
  • [11] Grohe M, 2020, Arxiv, DOI arXiv:2012.14300
  • [12] 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)
  • [13] A Faster Isomorphism Test for Graphs of Small Degree
    Grohe, Martin
    Neuen, Daniel
    Schweitzer, Pascal
    [J]. 2018 IEEE 59TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2018, : 89 - 100
  • [14] Isomorphism Testing for Graphs of Bounded Rank Width
    Grohe, Martin
    Schweitzer, Pascal
    [J]. 2015 IEEE 56TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2015, : 1010 - 1029
  • [15] STRUCTURE THEOREM AND ISOMORPHISM TEST FOR GRAPHS WITH EXCLUDED TOPOLOGICAL SUBGRAPHS
    Grohe, Martin
    Marx, Daniel
    [J]. SIAM JOURNAL ON COMPUTING, 2015, 44 (01) : 114 - 159
  • [16] Hopcroft J.E., 1972, COMPLEXITY COMPUTER, P131
  • [17] IMMERMAN N., 1988, HONOR JURIS HARTMANI, P59, DOI [10.1007/978-1-4612-4478-35, DOI 10.1007/978-1-4612-4478-35]
  • [18] LOWER BOUND OF THE HADWIGER NUMBER OF GRAPHS BY THEIR AVERAGE DEGREE
    KOSTOCHKA, AV
    [J]. COMBINATORICA, 1984, 4 (04) : 307 - 316
  • [19] Fixed-Parameter Tractability of Graph Isomorphism in Graphs with an Excluded Minor
    Lokshtanov, Daniel
    Pilipczuk, Marcin
    Pilipczuk, Michal
    Saurabh, Saket
    [J]. PROCEEDINGS OF THE 54TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '22), 2022, : 914 - 923
  • [20] FIXED-PARAMETER TRACTABLE CANONIZATION AND ISOMORPHISM TEST FOR GRAPHS OF BOUNDED TREEWIDTH
    Lokshtanov, Daniel
    Pilipczuk, Marcin
    Pilipczuk, Michal
    Saurabh, Saket
    [J]. SIAM JOURNAL ON COMPUTING, 2017, 46 (01) : 161 - 189
1234