A polynomial-time algorithm for simple undirected graph isomorphism

Jing He, Jinjun Chen, Guangyan Huang, Jie Cao, Zhiwang Zhang, Hui Zheng, Peng Zhang, Roozbeh Zarei, Ferry Sansoto, Ruchuan Wang, Yimu Ji, Weibei Fan, Zhijun Xie, Xiancheng Wang, Mengjiao Guo, Chi Hung Chi, Paulo A. de Souza, Jiekui Zhang, Youtao Li, Xiaojun Chen & 4 others Yong Shi, David Green, Taraporewalla Kersi, André Van Zundert

Research output: Contribution to journalArticleResearchpeer-review

Abstract

The graph isomorphism problem is to determine two finite graphs that are isomorphic which is not known with a polynomial-time solution. This paper solves the simple undirected graph isomorphism problem with an algorithmic approach as NP=P and proposes a polynomial-time solution to check if two simple undirected graphs are isomorphic or not. Three new representation methods of a graph as vertex/edge adjacency matrix and triple tuple are proposed. A duality of edge and vertex and a reflexivity between vertex adjacency matrix and edge adjacency matrix were first introduced to present the core idea. Beyond this, the mathematical approval is based on an equivalence between permutation and bijection. Because only addition and multiplication operations satisfy the commutative law, we propose a permutation theorem to check fast whether one of two sets of arrays is a permutation of another or not. The permutation theorem was mathematically approved by Integer Factorization Theory, Pythagorean Triples Theorem, and Fundamental Theorem of Arithmetic. For each of two n-ary arrays, the linear and squared sums of elements were respectively calculated to produce the results.

Original languageEnglish
Article numbere5484
Number of pages24
JournalConcurrency and Computation-Practice & Experience
DOIs
Publication statusAccepted/In press - 16 Aug 2019

Keywords

  • equivalence between permutation and bijection
  • graph isomorphism
  • polynomial-time solution
  • reflexivity and duality
  • simple undirected graph
  • vertex/edge adjacency matrix

Cite this

He, J., Chen, J., Huang, G., Cao, J., Zhang, Z., Zheng, H., ... Van Zundert, A. (Accepted/In press). A polynomial-time algorithm for simple undirected graph isomorphism. Concurrency and Computation-Practice & Experience, [e5484]. https://doi.org/10.1002/cpe.5484
He, Jing ; Chen, Jinjun ; Huang, Guangyan ; Cao, Jie ; Zhang, Zhiwang ; Zheng, Hui ; Zhang, Peng ; Zarei, Roozbeh ; Sansoto, Ferry ; Wang, Ruchuan ; Ji, Yimu ; Fan, Weibei ; Xie, Zhijun ; Wang, Xiancheng ; Guo, Mengjiao ; Chi, Chi Hung ; de Souza, Paulo A. ; Zhang, Jiekui ; Li, Youtao ; Chen, Xiaojun ; Shi, Yong ; Green, David ; Kersi, Taraporewalla ; Van Zundert, André. / A polynomial-time algorithm for simple undirected graph isomorphism. In: Concurrency and Computation-Practice & Experience. 2019.
@article{6eb9771bc38c46bab6e9492ac9d36228,
title = "A polynomial-time algorithm for simple undirected graph isomorphism",
abstract = "The graph isomorphism problem is to determine two finite graphs that are isomorphic which is not known with a polynomial-time solution. This paper solves the simple undirected graph isomorphism problem with an algorithmic approach as NP=P and proposes a polynomial-time solution to check if two simple undirected graphs are isomorphic or not. Three new representation methods of a graph as vertex/edge adjacency matrix and triple tuple are proposed. A duality of edge and vertex and a reflexivity between vertex adjacency matrix and edge adjacency matrix were first introduced to present the core idea. Beyond this, the mathematical approval is based on an equivalence between permutation and bijection. Because only addition and multiplication operations satisfy the commutative law, we propose a permutation theorem to check fast whether one of two sets of arrays is a permutation of another or not. The permutation theorem was mathematically approved by Integer Factorization Theory, Pythagorean Triples Theorem, and Fundamental Theorem of Arithmetic. For each of two n-ary arrays, the linear and squared sums of elements were respectively calculated to produce the results.",
keywords = "equivalence between permutation and bijection, graph isomorphism, polynomial-time solution, reflexivity and duality, simple undirected graph, vertex/edge adjacency matrix",
author = "Jing He and Jinjun Chen and Guangyan Huang and Jie Cao and Zhiwang Zhang and Hui Zheng and Peng Zhang and Roozbeh Zarei and Ferry Sansoto and Ruchuan Wang and Yimu Ji and Weibei Fan and Zhijun Xie and Xiancheng Wang and Mengjiao Guo and Chi, {Chi Hung} and {de Souza}, {Paulo A.} and Jiekui Zhang and Youtao Li and Xiaojun Chen and Yong Shi and David Green and Taraporewalla Kersi and {Van Zundert}, Andr{\'e}",
year = "2019",
month = "8",
day = "16",
doi = "10.1002/cpe.5484",
language = "English",
journal = "Concurrency and Computation-Practice & Experience",
issn = "1532-0626",
publisher = "Wiley-Blackwell",

}

He, J, Chen, J, Huang, G, Cao, J, Zhang, Z, Zheng, H, Zhang, P, Zarei, R, Sansoto, F, Wang, R, Ji, Y, Fan, W, Xie, Z, Wang, X, Guo, M, Chi, CH, de Souza, PA, Zhang, J, Li, Y, Chen, X, Shi, Y, Green, D, Kersi, T & Van Zundert, A 2019, 'A polynomial-time algorithm for simple undirected graph isomorphism', Concurrency and Computation-Practice & Experience. https://doi.org/10.1002/cpe.5484

A polynomial-time algorithm for simple undirected graph isomorphism. / He, Jing; Chen, Jinjun; Huang, Guangyan; Cao, Jie; Zhang, Zhiwang; Zheng, Hui; Zhang, Peng; Zarei, Roozbeh; Sansoto, Ferry; Wang, Ruchuan; Ji, Yimu; Fan, Weibei; Xie, Zhijun; Wang, Xiancheng; Guo, Mengjiao; Chi, Chi Hung; de Souza, Paulo A.; Zhang, Jiekui; Li, Youtao; Chen, Xiaojun; Shi, Yong; Green, David; Kersi, Taraporewalla; Van Zundert, André.

In: Concurrency and Computation-Practice & Experience, 16.08.2019.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - A polynomial-time algorithm for simple undirected graph isomorphism

AU - He, Jing

AU - Chen, Jinjun

AU - Huang, Guangyan

AU - Cao, Jie

AU - Zhang, Zhiwang

AU - Zheng, Hui

AU - Zhang, Peng

AU - Zarei, Roozbeh

AU - Sansoto, Ferry

AU - Wang, Ruchuan

AU - Ji, Yimu

AU - Fan, Weibei

AU - Xie, Zhijun

AU - Wang, Xiancheng

AU - Guo, Mengjiao

AU - Chi, Chi Hung

AU - de Souza, Paulo A.

AU - Zhang, Jiekui

AU - Li, Youtao

AU - Chen, Xiaojun

AU - Shi, Yong

AU - Green, David

AU - Kersi, Taraporewalla

AU - Van Zundert, André

PY - 2019/8/16

Y1 - 2019/8/16

N2 - The graph isomorphism problem is to determine two finite graphs that are isomorphic which is not known with a polynomial-time solution. This paper solves the simple undirected graph isomorphism problem with an algorithmic approach as NP=P and proposes a polynomial-time solution to check if two simple undirected graphs are isomorphic or not. Three new representation methods of a graph as vertex/edge adjacency matrix and triple tuple are proposed. A duality of edge and vertex and a reflexivity between vertex adjacency matrix and edge adjacency matrix were first introduced to present the core idea. Beyond this, the mathematical approval is based on an equivalence between permutation and bijection. Because only addition and multiplication operations satisfy the commutative law, we propose a permutation theorem to check fast whether one of two sets of arrays is a permutation of another or not. The permutation theorem was mathematically approved by Integer Factorization Theory, Pythagorean Triples Theorem, and Fundamental Theorem of Arithmetic. For each of two n-ary arrays, the linear and squared sums of elements were respectively calculated to produce the results.

AB - The graph isomorphism problem is to determine two finite graphs that are isomorphic which is not known with a polynomial-time solution. This paper solves the simple undirected graph isomorphism problem with an algorithmic approach as NP=P and proposes a polynomial-time solution to check if two simple undirected graphs are isomorphic or not. Three new representation methods of a graph as vertex/edge adjacency matrix and triple tuple are proposed. A duality of edge and vertex and a reflexivity between vertex adjacency matrix and edge adjacency matrix were first introduced to present the core idea. Beyond this, the mathematical approval is based on an equivalence between permutation and bijection. Because only addition and multiplication operations satisfy the commutative law, we propose a permutation theorem to check fast whether one of two sets of arrays is a permutation of another or not. The permutation theorem was mathematically approved by Integer Factorization Theory, Pythagorean Triples Theorem, and Fundamental Theorem of Arithmetic. For each of two n-ary arrays, the linear and squared sums of elements were respectively calculated to produce the results.

KW - equivalence between permutation and bijection

KW - graph isomorphism

KW - polynomial-time solution

KW - reflexivity and duality

KW - simple undirected graph

KW - vertex/edge adjacency matrix

UR - http://www.scopus.com/inward/record.url?scp=85070780482&partnerID=8YFLogxK

U2 - 10.1002/cpe.5484

DO - 10.1002/cpe.5484

M3 - Article

JO - Concurrency and Computation-Practice & Experience

JF - Concurrency and Computation-Practice & Experience

SN - 1532-0626

M1 - e5484

ER -