Description Graphs, Matrix-Power Stabilizations and Graph Isomorphism

[Submitted on 9 Nov 2022] Authors:Rui Xue (State Key Laboratory of Information Security, Institute of Information Engineering, CAS) Download PDF Abstract: It is confirmed in this work that the graph isomorphism can be tested in polynomial time, which resolves a longstanding problem in the theory of computation. The contributions are in three phases as follows. 1. A description graph $tilde{A}$ to a given graph $A$ is introduced so that labels to vertices and edges of $tilde{A}$ indicate the identical or different amounts of walks of any sort in any length between vertices in $A$. Three processes are then developed to obtain description graphs. They reveal relations among matrix power, spectral decomposition and adjoint matrices, which is of independent interest. 2. We show that the stabilization of description graphs can be implemented via matrix-power stabilization, a new approach to distinguish vertices and edges to graphs. The approach is proven to be equivalent in the partition of vertices to Weisfeiler-Lehman (WL for short) process. The specific Square-and-Substitution (SaS) process is more succinct than WL process. The vertex partitions to our stable graphs are proven to be emph{strongly} equitable partitions, which is important in the proofs of our main conclusion. Some properties on stable graphs are also explored. 3. A class of graphs named binding graphs is proposed and proven to be graph-isomorphism complete. The vertex partition to the stable graph of a binding graph is the automorphism partition, which allows us to confirm graph-isomorphism problem is in complexity class $mathtt{P}$. Since the binding graph to a graph is so simple in construction, our approach can be readily applied in practice. Submission history From: Rui Xue [view email] [v1] Wed, 9 Nov 2022 05:52:55 UTC (64 KB)
Read More