betaFeedback

WorksComputer Science

Subgraph Isomorphism, Integer Linear Programming, and Lattices: A Linear Algebraic Framework

Abstract

The subgraph isomorphism problem (SGI) asks a deceptively simple question: is a graph B found inside a parent graph A? Famously NP-complete and the subject of volumes of study, attempts to practically solve subgraph problems typically require specialized software or the focused application of problem-specific theoretical knowledge. Here we present a straightforward linear framework that neatly joins SGI to lattice theory and constrained satisfiability and, importantly, yields an easily implemented algorithm that naturally leverages consumer-grade hardware and off-the-shelf libraries to compete with state-of-the-art specialized solvers. We additionally show practical realizations in approachable settings, along with some benchmarks that reduce 6+ hour computations to seconds. Aimed at readability, we develop a series of computable algebraic invariants and demonstrate their application to familiar problems such as the Knight's Tour, with a focus on providing an accessible entry point for researchers in graph theory, abstract algebra, and students in general.

Introduction

The subgraph isomorphism (SGI) problem asks an apparently simple question: when is one graph contained inside another? Framed another way, given a pattern graph GBG_B on MM vertices and a target graph GAG_A on N≥MN \ge M vertices, how hard is it to find a copy of GBG_B inside GAG_A—or prove that no such copy exists? Easy to state, subgraph isomorphism is famously NP-complete [1], generalizing both the graph isomorphism problem [2, 3, 4] and the Hamiltonian cycle problem, with direct relevance to chemical informatics, circuit layout, computer vision, and network analysis.

While both general and constrained versions of this problem have been extensively studied using deep insights from combinatorics, backtracking search (Ullmann [5], VF2 [6], RI [7], VF3 [8], FASTiso [9]), constraint programming and cutting planes (LAD [10], Glasgow [11, 12, 13]), and database indexing (TurboISO [14], DAF [15]), these algorithmic paradigms are typically developed separately from the spectral and Smith normal form (SNF) invariants of algebraic graph theory [16, 17, 18, 19, 20]—which, conversely, have historically been restricted to square (M=NM = N) graph isomorphism and cospectrality.

This paper bridges these two worlds through the lens of linear algebra, integer linear programming (ILP), and lattice theory. By treating the rectangular matrix commutator PA−BPPA - BP as a global linear operator rather than a collection of decoupled Boolean clauses, we:

  1. unify square graph isomorphism (M=NM = N) and rectangular subgraph isomorphism (M≤NM \le N, both induced and non-induced) in a single MNMN-variable Kronecker operator framework (§ 2) that naturally exploits modern multi-core CP-SAT and ILP solvers (§ 7–§ 8);

  1. construct an explicit unimodular cycle basis LL for the doubly-stochastic lattice that connects the commutator kernel directly to generalized cospectrality and affine lattice norm minimization (§ 3–§ 4.3); and

  1. introduce a projection of the rectangular commutator onto the (M−1)(N−1)(M-1)(N-1)-dimensional zero-sum difference lattice LM,N(0)\mathcal{L}^{(0)}_{M,N} that eliminates unmatched vertex asymmetries and boundary edges, yielding a new Subgraph SNF Interlacing Theorem (Theorem 7) and polynomial-time refutation certificates for Kuratowski obstructions, longest cycles, and Knight’s Tours (§ 4.4–§ 6).

Aimed at approachability, the goal is to show how the classical linear commutator of graph isomorphism extends directly to rectangular subgraph isomorphism, offering a clean set of algebraic and computational in-roads to the problem with as simple a presentation as possible.

Subgraph Isomorphism and Linear Algebra

From Square Permutations to the Kronecker Commutator (M=NM=N)

Consider two graphs, GAG_A and GBG_B, with corresponding adjacency matrices A∈{0,1}N×NA \in\{0,1\}^{N \times N} and B∈{0,1}M×MB \in\{0,1\}^{M \times M}, respectively. In the special case where both graphs have the same number of vertices (M=NM=N), Graph isomorphism between GAG_A and GBG_B (GA≃GBG_A \simeq G_B) holds if and only if there exists a square permutation matrix P∈{0,1}N×NP \in\{0,1\}^{N \times N} such that:

PAPT=BPAP^T = B

Because PP is orthogonal (PT=P−1P^T=P^{-1}), multiplying on the right by PP yields the classical linear commutator equation:

PA−BP=0(1)PA-BP=0 \tag*{(1)}

Though previous work has often framed (1) as a doubly-stochastic continuous relaxation [21, 22, 23] or via ℓ1\ell_1 penalty linearizations for weighted graph matching and edit distance [24, 25], one can utilize the vectorization operator (vec) and the Kronecker product (⊗\otimes) [26] to arrive at an exact linear system. Recall that for matrices XX, YY, and ZZ of compatible dimensions:

vec⁡(XYZ)=(X⊗ZT)⋅vec⁡(Y)(2)\operatorname{vec}(XYZ)=(X\otimes Z^T)\cdot\operatorname{vec}(Y) \tag*{(2)}

Here, vec⁡(Y)\operatorname{vec}(Y) stacks the rows of matrix YY into a single column vector, and the Kronecker product X⊗ZTX\otimes Z^T forms a block matrix where each entry of XX multiplies the entire matrix ZTZ^T. Applying (2) to (1) (IPA−BPI=0IPA-BPI=0, for symmetric undirected graphs where A=ATA=A^T) yields the homogeneous linear system:

(I⊗A−B⊗I)⋅vec⁡(P)=0(3)(I\otimes A-B\otimes I)\cdot\operatorname{vec}(P)=0 \tag*{(3)}

where vec⁡(P)\operatorname{vec}(P) is an N2×1N^2 \times1 column vector representing the vectorized permutation matrix PP. Note that this re-framing in itself remains identical to the linear graph isomorphism approaches outlined in [21, 22] but, importantly, unlocks a richer array of algebraic tools, as we will see in subsequent sections. (3) therefore forms the basis of our linear algebraic approach, as it follows directly from (3) that all permutation matrices establishing GA≃GBG_A \simeq G_B exist within the nullspace:

Null⁡(I⊗A−B⊗I)\operatorname{Null}(I\otimes A-B\otimes I)

Subgraph Isomorphism

Subgraph isomorphism generalizes this question from “are two graphs the same?” to “is this graph a subgraph of the other?”. Formally, for graphs GAG_A on NN vertices and GBG_B on MM (with M<NM < N), one is searching for an injective mapping π:VB→VA\pi: V_B \to V_A embedding the smaller graph GBG_B into the larger target GAG_A. In the linear formulation, this mapping is represented by a rectangular binary matrix P∈{0,1}M×NP \in\{0,1\}^{M \times N} where Pi,v=1⟺π(i)=vP_{i,v} = 1 \Longleftrightarrow\pi(i) = v. For PP to represent a valid one-to-one injection, each row must sum to 1 and each column to at most 1:

P1N=1MandPT1M≤1NP\mathbf{1}_N = \mathbf{1}_M \qquad\text{and} \qquad P^T\mathbf{1}_M \leq\mathbf{1}_N

where 1N\mathbf{1}_N denotes the N×1N \times1 all-ones vector. Whereas traditional integer programming approaches to subgraph matching and graph edit distance introduce O(M2N2)O(M^2N^2) edge-product variables or dummy-vertex padding [25, 27, 28], even though PP is now rectangular and no longer orthogonal (PTP≠INP^T P \ne I_N), the linear commutator PA−BPPA - BP from Equation (1) still directly captures both non-induced subgraph isomorphism (GB⊆GAG_B \subseteq G_A, where GAG_A must contain all edges of GBG_B but may include extra edges) and induced subgraph isomorphism (GB⊆indGAG_B \subseteq_{\mathrm{ind}} G_A, where both edges and non-edges must be preserved, i.e., GB⊆GAG_B \subseteq G_A and GˉB⊆GˉA\bar{G}_B \subseteq\bar{G}_A for the complement graphs Aˉ=JN−IN−A\bar{A} = J_N - I_N - A and Bˉ=JM−IM−B\bar{B} = J_M - I_M - B, with JN=1N1NTJ_N = \mathbf{1}_N\mathbf{1}_N^T the all-ones matrix):

Theorem 1 (Rectangular Commutator Inequalities for Subgraph Isomorphism). Let P∈{0,1}M×NP \in\{0,1\}^{M \times N} be a rectangular injection matrix (P1N=1MP\mathbf{1}_N = \mathbf{1}_M, PT1M≤1NP^T\mathbf{1}_M \leq\mathbf{1}_N). Then:

  1. PP defines a non-induced subgraph isomorphism (GB⊆GAG_B \subseteq G_A) if and only if:

PA−BP≥0(4)PA - BP \geq0 \tag*{(4)}
  1. PP defines an induced subgraph isomorphism (GB⊆indGAG_B \subseteq_{\mathrm{ind}} G_A) if and only if both GBG_B and its complement GˉB\bar{G}_B satisfy the commutator inequality:

PA−BP≥0andPAˉ−BˉP≥0(5)PA - BP \geq0 \qquad\text{and} \qquad P\bar{A} - \bar{B}P \geq0 \tag*{(5)}

Proof. Let pattern vertex ii map to target vertex π(i)∈VA\pi(i) \in V_A. Expanding entry (i,v)(i,v) of the rectangular commutator PA−BPPA - BP gives:

(PA−BP)i,v=∑u=1NPi,uAu,v−∑j=1MBi,jPj,v=Aπ(i),v−∑j=1MBi,jPj,v(PA - BP)_{i,v} = \sum_{u=1}^{N} P_{i,u}A_{u,v} - \sum_{j=1}^{M} B_{i,j}P_{j,v} = A_{\pi(i),v} - \sum_{j=1}^{M} B_{i,j}P_{j,v}

Because each column vv of PP contains at most one non-zero entry, there are two cases:

  • Part 1 (Target vertex vv is unmatched, Pj,v=0 ∀jP_{j,v} = 0\ \forall j): The second term vanishes and (PA−BP)i,v=Aπ(i),v≥0(PA - BP)_{i,v} = A_{\pi(i),v} \geq0 holds automatically (and identically (PAˉ−BˉP)i,v=Aˉπ(i),v≥0(P\bar{A} - \bar{B}P)_{i,v} = \bar{A}_{\pi(i),v} \geq0). Unmatched target vertices impose no constraints on boundary edges leaving the embedded subgraph.

  • Part 2 (Target vertex vv is matched to a unique pattern vertex j∗=π−1(v)j^* = \pi^{-1}(v), Pj∗,v=1P_{j^*,v} = 1): Here all other entries in column vv are zero, so the commutator entry simplifies to:

(PA−BP)i,v=Aπ(i),π(j∗)−Bi,j∗=(PAPT−B)i,j∗∈{−1,0,+1}(PA - BP)_{i,v} = A_{\pi(i),\pi(j^*)} - B_{i,j^*} = (PAP^T - B)_{i,j^*} \in\{-1,0,+1\}

Enforcing PA−BP≥0PA - BP \geq0 forbids −1-1, which holds if and only if Aπ(i),π(j∗)≥Bi,j∗A_{\pi(i),\pi(j^*)} \geq B_{i,j^*} for all mapped pairs, establishing non-induced SGI (Equation (4a)). By the exact same argument on the complement graphs, enforcing PAˉ−BˉP≥0P\bar{A} - \bar{B}P \geq0 holds if and only if Aˉπ(i),π(j∗)≥Bˉi,j∗\bar{A}_{\pi(i),\pi(j^*)} \geq\bar{B}_{i,j^*} (or equivalently Aπ(i),π(j∗)≤Bi,j∗A_{\pi(i),\pi(j^*)} \leq B_{i,j^*}) for all i≠j∗i \ne j^*. Combining both inequalities forces Aπ(i),π(j∗)=Bi,j∗A_{\pi(i),\pi(j^*)} = B_{i,j^*} across all matched pairs, establishing induced SGI (Equation (4b)).

Note that for any binary row-stochastic matrix P∈{0,1}M×NP \in\{0,1\}^{M \times N} (P1N=1MP1_N = 1_M) and binary adjacency matrices A,B∈{0,1}A,B \in\{0,1\}, the upper bound (PA−BP)i,v=Aπ(i),v−(BP)i,v≤Aπ(i),v≤1(PA-BP)_{i,v}=A_{\pi(i),v}-(BP)_{i,v}\le A_{\pi(i),v}\le1 (and similarly for Aˉ,Bˉ\bar{A},\bar{B}) holds automatically at every entry (i,v)(i,v) and serves to tighten continuous LP relaxations. Written out entry-by-entry, each row of PA−BP≥0PA-BP\ge0 enforces ∑u∈NA(v)Pi,u≥∑j∈NB(i)Pj,v\sum_{u\in N_A(v)}P_{i,u}\ge\sum_{j\in N_B(i)}P_{j,v}, recovering the standard linear adjacency-implication inequalities used in 0–1 integer and pseudo-Boolean subgraph encodings [13, 24]. Crucially, however, preserving these inequalities in their global matrix-operator form PA−BPPA-BP rather than treating them as isolated Boolean clauses unlocks a direct algebraic bridge to lattice projection and Smith normal form invariant-factor interlacing across the entire operator (§ 4.1). (We also note in passing that the matrix-operator form immediately implies polynomial walk monotonicity: because P,A,B≥0P,A,B\ge0, PA≥BPPA\ge BP implies PAk≥BkPPA^k\ge B^kP and hence Pf(A)−f(B)P≥0Pf(A)-f(B)P\ge0 for any polynomial ff with non-negative coefficients. While all empirical benchmarks in Sections 6–7 use only the base k=1k=1 system below, higher-power walk inequalities offer a natural family of optional auxiliary linear constraints that can be appended without introducing additional decision variables.)

Applying the vectorization identity (Equation (2)) to Equations (4a) and (4b) yields the MN×MNMN\times MN Kronecker operator form of subgraph isomorphism:

0≤(IM⊗A−B⊗IN)⋅vec⁡(P)≤1(6)0 \le(I_M \otimes A-B\otimes I_N)\cdot\operatorname{vec}(P)\le1 \tag*{(6)}
0≤(IM⊗Aˉ−Bˉ⊗IN)⋅vec⁡(P)≤1(7)0 \le(I_M \otimes\bar{A}-\bar{B}\otimes I_N)\cdot\operatorname{vec}(P)\le1 \tag*{(7)}

Spectral Properties

Eigenvalue Structure

Returning to the Kronecker operator I⊗A−B⊗II\otimes A-B\otimes I in Equation (3), its eigenvalues and eigenvectors follow directly from the classical Sylvester–Kronecker spectrum of AA and BB [16, 26].

Theorem 2 (Spectrum of I⊗A−B⊗II\otimes A-B\otimes I [26]). If {λA,i}\{\lambda_{A,i}\} and {λB,j}\{\lambda_{B,j}\} are the eigenvalues of symmetric adjacency matrices AA and BB with corresponding eigenvectors viv_i and uju_j, then I⊗A−B⊗II\otimes A-B\otimes I has eigenvalues {λA,i−λB,j}\{\lambda_{A,i}-\lambda_{B,j}\} for all i,ji,j with corresponding eigenvectors wi,j=uj⊗viw_{i,j}=u_j\otimes v_i.

Proof. Recall the mixed-product property of Kronecker products: (P⊗Q)(R⊗S)=(PR)⊗(QS)(P\otimes Q)(R\otimes S)=(PR)\otimes(QS). Let wi,j=uj⊗viw_{i,j}=u_j\otimes v_i, where uju_j and viv_i are the jj-th and ii-th eigenvectors of BB and AA, respectively:

(I⊗A)wi,j=(I⊗A)(uj⊗vi)=(Iuj)⊗(Avi)=uj⊗(λA,ivi)=λA,iwi,j(I\otimes A)w_{i,j}=(I\otimes A)(u_j\otimes v_i)=(Iu_j)\otimes(Av_i)=u_j\otimes(\lambda_{A,i}v_i)=\lambda_{A,i}w_{i,j}

And, by symmetry:

(B⊗I)wi,j=(Buj)⊗(Ivi)=(λB,juj)⊗vi=λB,jwi,j(B\otimes I)w_{i,j}=(Bu_j)\otimes(Iv_i)=(\lambda_{B,j}u_j)\otimes v_i=\lambda_{B,j}w_{i,j}

Because wi,jw_{i,j} is an eigenvector of both (I⊗A)(I\otimes A) and (B⊗I)(B\otimes I), subtracting the two equations yields:

((I⊗A)−(B⊗I))wi,j=(λA,i−λB,j)wi,j((I\otimes A)-(B\otimes I))w_{i,j}=(\lambda_{A,i}-\lambda_{B,j})w_{i,j}

Thus {λA,i−λB,j}\{\lambda_{A,i}-\lambda_{B,j}\} for all i,ji,j are the exact eigenvalues of the Kronecker commutator.

An immediate and direct consequence of Theorem 2 is a clean characterization of cospectral graphs [29, 30] via nullspace dimensions:

Theorem 3 (Nullspace Dimension and Cospectrality). Let NAB=dim⁡Null⁡(I⊗A−B⊗I)N_{AB}=\dim\operatorname{Null}(I\otimes A-B\otimes I). Then:

NAA=NAB=NBB⟺Spec⁡(GA)=Spec⁡(GB)(8)N_{AA}=N_{AB}=N_{BB}\Longleftrightarrow\operatorname{Spec}(G_A)=\operatorname{Spec}(G_B) \tag*{(8)}

That is, if the rank of the Kronecker commutator is consistent across I⊗A−A⊗II \otimes A - A \otimes I, I⊗B−B⊗II \otimes B - B \otimes I, and I⊗A−B⊗II \otimes A - B \otimes I, then GAG_A is cospectral to GBG_B.

Proof. Let {μ1,…,μk}\{\mu_1,\ldots,\mu_k\} denote the union of distinct eigenvalues of the symmetric matrices AA and BB, with multiplicities mr≥0m_r \ge0 in Spec⁡(GA)\operatorname{Spec}(G_A) and nr≥0n_r \ge0 in Spec⁡(GB)\operatorname{Spec}(G_B). Because AA and BB are orthogonally diagonalizable, dim⁡Null⁡(I⊗A−B⊗I)\dim\operatorname{Null}(I \otimes A - B \otimes I) equals the number of pairs (i,j)(i,j) for which λA,i−λB,j=0\lambda_{A,i} - \lambda_{B,j} = 0 by Theorem 2. Thus NAB=∑r=1kmrnrN_{AB} = \sum_{r=1}^{k}m_rn_r, and similarly NAA=∑r=1kmr2N_{AA} = \sum_{r=1}^{k}m_r^2 and NBB=∑r=1knr2N_{BB} = \sum_{r=1}^{k}n_r^2. Subtracting 2NAB2N_{AB} from NAA+NBBN_{AA} + N_{BB} yields the sum of squares:

NAA−2NAB+NBB=∑r=1k(mr−nr)2≥0.N_{AA} - 2N_{AB} + N_{BB} = \sum_{r=1}^{k}(m_r-n_r)^2 \ge0.

Consequently, NAA=NAB=NBBN_{AA} = N_{AB} = N_{BB} implies ∑r=1k(mr−nr)2=0\sum_{r=1}^{k}(m_r-n_r)^2 = 0, which holds if and only if mr=nrm_r = n_r for every r∈{1,…,k}r \in\{1,\ldots,k\}, i.e., Spec⁡(GA)=Spec⁡(GB)\operatorname{Spec}(G_A) = \operatorname{Spec}(G_B).

Graph Isomorphism as a Lattice Problem

Though it has been known for some time that lattice isomorphism is at least as hard as graph isomorphism [31, 32, 33], the construction we present in the next section provides an explicit construction—and some novel, surprising outcomes from that construction. Specifically, we show that: there exists an explicit lattice construction for any graph isomorphism problem, graph isomorphism maps to a tightly bound shortest vector problem (SVP), and the Smith normal form allows some graph invariants that allow a powerful set of polynomial-time a priori proofs about (sub)graph isomorphism generally, and that graphs with identical SNF invariants are Generalized Cospectral. We follow with some practical realizations of these properties in some familiar settings, including some explicit linear constructions of permutation matrices directly from the kernels of these systems.

Graph Isomorphism and Lattices

Equation (3) (and more generally Equation (5)) introduced a natural integer linear programming (ILP) framing over the space of possible permutations that would satisfy forms of graph (sub)isomorphism [34, 35, 36]. Without loss of generality, we first analyze the square graph isomorphism framing of Equation (3):

(I⊗A−B⊗I)⋅vec⁡(P)=0(I \otimes A - B \otimes I) \cdot\operatorname{vec}(P) = 0

Which is to say, if GA≅GBG_A \cong G_B, then a {0,1}N2\{0,1\}^{N^2} vector exists satisfying the above. Of course, one knows that PP is a permutation matrix and a considerably tighter framing is possible. Framed differently, any solution to this equation lies in the intersection of the continuous RN2\mathbb{R}^{N^2} kernel of the Kronecker commutator and the integer lattice defined by all possible permutation bases. The outer convex hull containing the space of these solutions is known as the Birkhoff Polytope [37].

Doubly-Stochastic Permutation Basis LL

The space of all permutation matrices admits a surprisingly clean geometric construction via discrete lattices.

Recall that a lattice is a discrete additive subgroup of RN2\mathbb{R}^{N^2} generated by integer combinations of basis vectors y=Lz\mathbf{y} = L\mathbf{z} (z∈Zd\mathbf{z} \in\mathbb{Z}^d). In N×NN \times N matrix space (dim⁡=N2\dim= N^2), requiring all NN row sums and all NN column sums of a matrix XX to equal a common scalar cc (X1=c1X\mathbf{1} = c\mathbf{1} and XT1=c1X^{T}\mathbf{1} = c\mathbf{1}) imposes (N−1)+(N−1)=2N−2(N-1)+(N-1)=2N-2 independent linear equations. Consequently, the subspace of generalized doubly-stochastic matrices has dimension [37]:

d=N2−(2N−2)=(N−1)2+1d = N^2 - (2N-2) = (N-1)^2+1

Rather than enforcing row and column sum equations externally, we can construct an explicit integral basis matrix L∈{0,1}N2×dL \in\{0,1\}^{N^2 \times d} directly from elementary permutation cycles anchored at vertex 0:

  1. The Identity (1 column): vec⁡(IN)\operatorname{vec}(I_N).

  1. Primary 2-Cycles ((N−1)(N-1) columns): The vectorized star transpositions vec⁡(P(0,i))\operatorname{vec}(P_{(0,i)}) for i∈{1,…,N−1}i \in\{1,\ldots,N-1\}.

  1. Secondary 3-Cycles ((N−1)(N−2)(N-1)(N-2) columns): The vectorized anchored 3-cycles vec⁡(P(0,i,j))\operatorname{vec}(P_{(0,i,j)}) for all ordered pairs 1≤i≠j≤N−11 \le i \ne j \le N-1.

Stacking these 1+(N−1)+(N−1)(N−2)=(N−1)2+11+(N-1)+(N-1)(N-2)=(N-1)^2+1 elementary cycle permutations forms an explicit unimodular {0,1}\{0,1\} basis matrix L∈{0,1}N2×dL \in\{0,1\}^{N^2 \times d} for the integer doubly-stochastic lattice:

L(Zd)={vec⁡(X)∈ZN2:X1=c1 and XT1=c1, where c=1dTz=∑k=1dzk∈Z}(9)L(\mathbb{Z}^d)=\left\{\operatorname{vec}(X)\in\mathbb{Z}^{N^2}:X\mathbf{1}=c\mathbf{1}\ \text{and}\ X^{T}\mathbf{1}=c\mathbf{1},\ \text{where}\ c=\mathbf{1}_d^{T}z=\sum_{k=1}^{d}z_k\in\mathbb{Z}\right\} \tag*{(9)}

Because every column of LL is a permutation matrix with row and column sum 1, substituting vec⁡(X)=Lz\operatorname{vec}(X)=Lz (z∈Zdz\in\mathbb{Z}^d) into Equation (3) automatically enforces equal row and column sums and projects the Kronecker commutator directly onto the permutation lattice:

(I⊗A−B⊗I)L⋅z=0(z∈Zd)(10)(I\otimes A-B\otimes I)L\cdot z=0 \qquad(z\in\mathbb{Z}^d) \tag*{(10)}

or, left-multiplying by LTL^{T} to obtain a square symmetric d×dd\times d operator on Zd\mathbb{Z}^d:

LT(I⊗A−B⊗I)L⋅z=0(z∈Zd)(11)L^{T}(I\otimes A-B\otimes I)L\cdot z=0 \qquad(z\in\mathbb{Z}^d) \tag*{(11)}

Though we’ll proceed with Eq 8 for the next section, Eq 9 will form the basis of relations through the most of rest of this paper we’ll often refer to it by short hand K(A,B)K(A,B), though will keep it in its expanded form when readability dictates.

Projection onto the Lattice and the Smith Normal Form

Because Equation (11) is a homogeneous integer linear system over Z\mathbb{Z} [34, 35], we can compute its Smith normal form (SNF) [18, 38, 39] in polynomial time [40, 41]:

USV=SNF⁡((I⊗A−B⊗I)L)(12)USV=\operatorname{SNF}((I\otimes A-B\otimes I)L) \tag*{(12)}

where UU and VV are unimodular integer matrices (det⁡U,det⁡V∈{±1}\det U,\det V\in\{\pm1\}) and S=diag⁡(s1,…,sr,0,…,0)S=\operatorname{diag}(s_1,\ldots,s_r,0,\ldots,0) is diagonal with elementary integer divisors satisfying s1∣s2∣⋯∣srs_1\mid s_2\mid\cdots\mid s_r.

For example, on the smallest cospectral non-isomorphic pair (N=5N = 5, Figure 1)—the star GA=K1,4G_A = K_{1,4} and the 4-cycle plus isolated vertex GB=C4∪K1G_B = C_4 \cup K_1, which share spectrum {−2,0,0,0,+2}\{-2, 0, 0, 0, +2\}—the unprojected 25×2525 \times25 commutator nullspaces are of equal dimension (NAA=NAB=NBB=11N_{AA} = N_{AB} = N_{BB} = 11 in Theorem 3). Projecting onto the 17-dimensional doubly-stochastic basis LL, however, immediately separates both their Smith normal form diagonals and their nullspace dimensions (Theorem 5):

Isometric 2D lattice slices comparing unprojected and doubly-stochastic lattice slices

Figure 1. Isometric 2D lattice slices comparing the unprojected integer nullspace Null⁡Z(I⊗A−B⊗I)\operatorname{Null}_{\mathbb{Z}}(I \otimes A-B \otimes I) (top row) and the Theorem 4 doubly-stochastic lattice L⋅Null⁡Z((I⊗A−B⊗I)L)L \cdot\operatorname{Null}_{\mathbb{Z}}((I \otimes A-B \otimes I)L) (bottom row) on the unit-sum slice c=1c=1 against the permutation norm sphere ∥v∥2=N\lVert v\rVert_2=\sqrt{N} (N=5N=5): (a) unprojected isomorphic slice Null⁡Z(I⊗A−P0AP0T⊗I)\operatorname{Null}_{\mathbb{Z}}(I \otimes A-P_0AP_0^{T} \otimes I) intersecting ∥v∥2=5\lVert v\rVert_2=\sqrt{5} at P1,P2P_1,P_2; (b) unprojected cospectral slice Null⁡Z(I⊗A−B⊗I)\operatorname{Null}_{\mathbb{Z}}(I \otimes A-B \otimes I) with interior c=0c=0 vectors w1\mathbf{w}_1 (∥w1∥2=2<5\lVert\mathbf{w}_1\rVert_2=2<\sqrt{5}) and empty annulus [4,6][\sqrt{4},\sqrt{6}]; (c) doubly-stochastic isomorphic slice (c=1c=1), where the interior ∥v∥2<5\lVert v\rVert_2<\sqrt{5} is empty, P1,P2P_1,P_2 lie on ∥v∥2=5\lVert v\rVert_2=\sqrt{5}, and non-permutations satisfy ∥v∥2≥N+4\lVert v\rVert_2\ge\sqrt{N+4}; (d) doubly-stochastic cospectral slice (c=1c=1), where c=0c=0 interior vectors are eliminated and all lattice points u1,u2\mathbf{u}_1,\mathbf{u}_2 are pushed outside to ∥v∥2≥N+4=3\lVert v\rVert_2\ge\sqrt{N+4}=3, leaving the entire ball around ∥v∥2=5\lVert v\rVert_2=\sqrt{5} empty.

diag⁡(SAA)=[16, 3, 010]⟹N~AA=10(LV0∈Z25×10),diag⁡(SBB)=[18, 23, 06]⟹N~BB=6(LV0∈Z25×6),diag⁡(SAB)=[111, 06]⟹N~AB=6(LV0∈Z25×6).\begin{aligned} \operatorname{diag}(S_{AA}) &= [1^6,\,3,\,0^{10}] &&\Longrightarrow\widetilde{N}_{AA} = 10 &&(LV_0 \in\mathbb{Z}^{25 \times10}),\\ \operatorname{diag}(S_{BB}) &= [1^8,\,2^3,\,0^6] &&\Longrightarrow\widetilde{N}_{BB} = 6 &&(LV_0 \in\mathbb{Z}^{25 \times6}),\\ \operatorname{diag}(S_{AB}) &= [1^{11},\,0^6] &&\Longrightarrow\widetilde{N}_{AB} = 6 &&(LV_0 \in\mathbb{Z}^{25 \times6}). \end{aligned}

Note that the SNF acts as an integer analog of Singular Value Decomposition and that the 0 valued invariants form a basis for integer valued solutions to 10. Specifically, if V0∈Zd×kV_0 \in\mathbb{Z}^{d \times k} denotes the columns of VV corresponding to zeros on the diagonal of SS, mapping V0V_0 back to the ambient space via LL yields the exact integral generator for the intersection of the commutator nullspace with the doubly-stochastic lattice:

vec⁡(P)=(L⋅V0)w(L⋅V0∈ZN2×k,  w∈Zk)(13)\operatorname{vec}(P) = (L \cdot V_0)w \qquad(L \cdot V_0 \in\mathbb{Z}^{N^2 \times k},\; w \in\mathbb{Z}^k) \tag*{(13)}

Having a look at the basis vectors that result from Eq. (13) for our classic cospectral example is illuminating

Figure 8. Un-Vectorizing the 10 Exact Kernel Basis Columns LV0∈Z25×10LV_0 \in\mathbb{Z}^{25 \times10} of (L⊗A−A⊗L)(L \otimes A - A \otimes L) (GA=K1,4)(G_A = K_{1,4}).

Note that 10 of the 11 raw basis vectors in LV0LV_0 resulting directly from the SNF are actual automorphism permutation matrices of K1,4K_{1,4}, which affine-linearly generate all ∣Aut⁡(K1,4)∣=4!=24|\operatorname{Aut}(K_{1,4})| = 4! = 24 automorphisms. Moreover, running the Lenstra–Lenstra–Lovász (LLL) lattice reduction algorithm [42] cleanly isolates I5I_5 and the nine elementary 2×22 \times2 leaf swaps. Though ∣Aut⁡(G)∣|\operatorname{Aut}(G)| can obviously grow much faster than the lattice dimension ≤N2\leq N^2 for larger graphs, this example gives a concrete, visual picture of how the integer commutator lattice intersects the Birkhoff polytope.

It is worth pausing to reflect that Equation (13) offers a fully realized, computable generator for doubly-stochastic, integer solutions to the intertwiner (Equation (1)) for graphs GAG_A and GBG_B. Moreover, though the lattice isomorphism problem (LIP) is known to be at least as hard as graph isomorphism (GI ≤P\leq_P LIP) [31, 32, 33], the above method demonstrates an explicit, constructive mapping from GI to integer lattices. In the algebraic graph theory literature, the Smith normal form has previously been applied to adjacency or Laplacian matrices directly [18, 43], to unprojected linear Diophantine systems [34, 35], and to the N×NN \times N walk matrix W(A)=[1,A1,…,AN−11]W(A) = [1, A1, \ldots, A^{N-1}1] to study generalized cospectrality [17, 19, 20, 44, 45, 46]. However, walk-matrix methods require the graph to be controllable (det⁡W(A)≠0\det W(A) \ne0) and degenerate on regular graphs where A1=k1A1 = k1 collapses W(A)W(A) to rank 1. Projecting the N2×N2N^2 \times N^2 Kronecker commutator directly onto the cycle basis LL bypasses walk vectors entirely—operating on arbitrary (including regular) graphs, capturing both GG and its complement G‾\overline{G} in a single operator, and extending naturally to rectangular subgraph isomorphism (M<NM < N, § 4.4).

Though this framing provides a rich theoretical landscape for investigation, three useful theorems present themselves immediately:

Theorem 4 (Graph Isomorphism is a Shortest Vector Problem). Let z∈Zdz \in\mathbb{Z}^{d} satisfy Equation (10) (or Equation (11)) on the unit-sum affine slice 1dTz=1\mathbf{1}_{d}^{T}z = 1, with ambient matrix v=Lz=vec⁡(X)∈ZN2v = Lz = \operatorname{vec}(X) \in\mathbb{Z}^{N^{2}}. Then:

∥Lz∥22=N(with 1dTz=1)⟺X∈SN and GA≃GB,\lVert Lz\rVert_{2}^{2} = N \quad\left(\text{with }\mathbf{1}_{d}^{T}z = 1\right) \Longleftrightarrow X \in S_{N}\ \text{and}\ G_{A} \simeq G_{B},

whereas every non-permutation solution with 1dTz=1\mathbf{1}_{d}^{T}z = 1 satisfies ∥Lz∥22≥N+2\lVert Lz\rVert_{2}^{2} \ge N + 2.

Proof. For any integer matrix X∈ZN×NX \in\mathbb{Z}^{N \times N} with row and column sums c=1dTz=1c = \mathbf{1}_{d}^{T}z = 1, we have ∑i,jXi,j=N\sum_{i,j} X_{i,j} = N. Since x(x−1)≥0x(x-1) \ge0 holds for every integer x∈Zx \in\mathbb{Z} with equality if and only if x∈{0,1}x \in\{0,1\}, and x(x−1)≥2x(x-1) \ge2 is even whenever x∈Z∖{0,1}x \in\mathbb{Z} \setminus\{0,1\}, summing over all entries yields:

∥Lz∥22=∑i,j=1NXi,j2=N+∑i,j=1NXi,j(Xi,j−1)≥N,\lVert Lz\rVert_{2}^{2} = \sum_{i,j=1}^{N} X_{i,j}^{2} = N + \sum_{i,j=1}^{N} X_{i,j}(X_{i,j}-1) \ge N,

with equality ∥Lz∥22=N⟺X∈{0,1}N×N\lVert Lz\rVert_{2}^{2} = N \Longleftrightarrow X \in\{0,1\}^{N \times N} (which with X1=1X\mathbf{1} = \mathbf{1} and XT1=1X^{T}\mathbf{1} = \mathbf{1} means X∈SNX \in S_{N}), and ∥Lz∥22≥N+2\lVert Lz\rVert_{2}^{2} \ge N + 2 whenever X∉SNX \notin S_{N}. Finally, for X=P∈SNX = P \in S_{N}, left-projection by LTL^{T} is lossless because PT(PA−BP)=A−PTBPP^{T}(PA-BP) = A-P^{T}BP is symmetric with zero diagonal, and the only symmetric matrix with zero diagonal in (IN⊗PT)Col⁡(L)⊥={r1T+1cT:1Tr=1Tc}(I_{N} \otimes P^{T})\operatorname{Col}(L)^{\perp} = \{r\mathbf{1}^{T}+\mathbf{1}c^{T}: \mathbf{1}^{T}r=\mathbf{1}^{T}c\} is 00; hence LTvec⁡(PA−BP)=0⟺PA−BP=0⟺GA≃GBL^{T}\operatorname{vec}(PA-BP)=0 \Longleftrightarrow PA-BP=0 \Longleftrightarrow G_{A}\simeq G_{B}.

Theorem 5 (Smith Normal Form Invariants and Generalized Cospectrality). Let N~AB=dim⁡Null⁡((I⊗A−B⊗I)L)\widetilde{N}_{AB} = \dim\operatorname{Null}((I \otimes A-B \otimes I)L). For graphs GA,GBG_{A},G_{B} satisfying NAA=NAB=NBBN_{AA}=N_{AB}=N_{BB} in Theorem 3 [17, 44]:

N~AA=N~AB=N~BB⟺Spec⁡(GA)=Spec⁡(GB) and Spec⁡(G‾A)=Spec⁡(G‾B).(14)\widetilde{N}_{AA}=\widetilde{N}_{AB}=\widetilde{N}_{BB}\Longleftrightarrow\operatorname{Spec}(G_{A})=\operatorname{Spec}(G_{B})\ \text{and}\ \operatorname{Spec}(\overline{G}_{A})=\operatorname{Spec}(\overline{G}_{B}). \tag*{(14)}

Proof. Let Pr(A)P_{r}(A) and Pr(B)P_{r}(B) denote the orthogonal projectors onto the μr\mu_{r}-eigenspaces Er(A)E_{r}(A) and Er(B)E_{r}(B), and set vr(A)=Pr(A)1v_{r}(A)=P_{r}(A)\mathbf{1} and vr(B)=Pr(B)1v_{r}(B)=P_{r}(B)\mathbf{1}. Any vec⁡(X)=Lz\operatorname{vec}(X)=Lz in Null⁡((I⊗A−B⊗I)L)\operatorname{Null}((I\otimes A-B\otimes I)L) satisfies XA=BXXA=BX (so XPr(A)=Pr(B)XXP_{r}(A)=P_{r}(B)X) together with X1=c1X\mathbf{1}=c\mathbf{1} and XT1=c1X^{T}\mathbf{1}=c\mathbf{1}, which implies Xvr(A)=cvr(B)Xv_{r}(A)=cv_{r}(B) and XTvr(B)=cvr(A)X^{T}v_{r}(B)=cv_{r}(A) for every rr. On the c=0c=0 slice, XX maps Er(A)∩vr(A)⊥E_{r}(A)\cap v_{r}(A)^{\perp} into Er(B)∩vr(B)⊥E_{r}(B)\cap v_{r}(B)^{\perp}, contributing N~AB(0)=∑r(mr−δvr(A)≠0)(nr−δvr(B)≠0)\widetilde{N}_{AB}^{(0)}=\sum_{r}(m_{r}-\delta_{v_{r}(A)\ne0})(n_{r}-\delta_{v_{r}(B)\ne0}) dimensions. Furthermore, taking the inner product with vr(B)v_{r}(B) yields

c∥vr(B)∥22=vr(B)TXvr(A)=(XTvr(B))Tvr(A)=c∥vr(A)∥22∀r.c\lVert v_{r}(B)\rVert_{2}^{2}=v_{r}(B)^{T}Xv_{r}(A)=(X^{T}v_{r}(B))^{T}v_{r}(A)=c\lVert v_{r}(A)\rVert_{2}^{2}\quad\forall r.

Thus a c≠0c\ne0 solution exists (adding +1+1 to N~AB(0)\widetilde{N}_{AB}^{(0)} as in N~AA\widetilde{N}_{AA} and N~BB\widetilde{N}_{BB}) if and only if ∥vr(A)∥2=∥vr(B)∥2\lVert v_{r}(A)\rVert_{2}=\lVert v_{r}(B)\rVert_{2} for all rr. Together with mr=nrm_{r}=n_{r} from NAA=NAB=NBBN_{AA}=N_{AB}=N_{BB}, equality of the main projections ∥vr(A)∥2=∥vr(B)∥2\lVert v_{r}(A)\rVert_{2}=\lVert v_{r}(B)\rVert_{2} across all eigenspaces is equivalent by the Johnson–Newman theorem [44] to Spec⁡(GA)=Spec⁡(GB)\operatorname{Spec}(G_{A})=\operatorname{Spec}(G_{B}) and Spec⁡(G‾A)=Spec⁡(G‾B)\operatorname{Spec}(\overline{G}_{A})=\operatorname{Spec}(\overline{G}_{B}).

Theorem 6 (Rational Denominators and Invariant Factors). Let M0(A,B)=(IN⊗A−B⊗IN)LN,N∈ZN2×(N−1)2M_{0}(A,B)=(I_{N}\otimes A-B\otimes I_{N})L_{N,N}\in\mathbb{Z}^{N^{2}\times(N-1)^{2}} denote the commutator restricted to the (N−1)2(N-1)^{2}-dimensional zero-sum difference lattice LN,N(0)\mathcal{L}_{N,N}^{(0)} (generated by LN,NL_{N,N} in § 4.4), with non-zero Smith normal form invariant factors s1∣s2∣⋯∣smax⁡s_{1}\mid s_{2}\mid\cdots\mid s_{\max} [18, 43]. Any regular rational orthogonal matrix Q∈O(N,Q)Q\in O(N,\mathbb{Q}) (QA−BQ=0QA-BQ=0, Q1=1Q\mathbf{1}=\mathbf{1}) of level ℓ=min⁡{m∈Z≥1:mQ∈ZN×N}\ell=\min\{m\in\mathbb{Z}_{\ge1}:mQ\in\mathbb{Z}^{N\times N}\} [17] decomposes around a reference permutation P0∈SNP_{0}\in S_{N} as Q=P0+X0Q=P_{0}+X_{0}, where vec⁡(X0)=LN,Nz0\operatorname{vec}(X_{0})=L_{N,N}z^{0} (z0∈Q(N−1)2z^{0}\in\mathbb{Q}^{(N-1)^{2}}) satisfies the inhomogeneous integer system M0(A,B)z0=−vec⁡(P0A−BP0)M_{0}(A,B)z^{0}=-\operatorname{vec}(P_{0}A-BP_{0}). Whenever M0(A,B)M_{0}(A,B) has full column rank (or on the normal component z0⊥Null⁡(M0(A,B))z^{0}\perp\operatorname{Null}(M_{0}(A,B))), the level ℓ\ell satisfies:

ℓ∣smax⁡.(15)\ell\mid s_{\max}. \tag*{(15)}

Consequently:

  1. Trivial Torsion Certifies Isomorphism: If smax⁡=1s_{\max}=1, then ℓ=1\ell=1, forcing Q∈O(N,Z)Q \in O(N,\mathbb{Z}) with Q1=1⟹GA≅GBQ\mathbf{1}=\mathbf{1} \Longrightarrow G_A \cong G_B.

  1. Immunity to Fractional Switching: If gcd⁡(smax⁡,p)=1\gcd(s_{\max},p)=1, the pair cannot be related by any such rational switching operation of level pp. In particular, if smax⁡s_{\max} is odd, no full-rank cospectral mate can be generated by standard Godsil–McKay switching (ℓ=2\ell=2) [29].

Proof. Because Q1=1=P01Q\mathbf{1}=\mathbf{1}=P_0\mathbf{1} and QT1=1=P0T1Q^T\mathbf{1}=\mathbf{1}=P_0^T\mathbf{1}, the difference X0=Q−P0X_0=Q-P_0 has zero row and column sums, so vec⁡(X0)=LN,Nz0\operatorname{vec}(X_0)=L_{N,N}z_0 for a unique coordinate vector z0∈Q(N−1)2z_0 \in\mathbb{Q}^{(N-1)^2} whose least common denominator equals ℓ\ell (since LN,NL_{N,N} is unimodular on LN,N(0)\mathcal{L}_{N,N}^{(0)}). Substituting Q=P0+X0Q=P_0+X_0 into QA−BQ=0QA-BQ=0 yields M0(A,B)z0=bM_0(A,B)z_0=b, where b=−vec⁡(P0A−BP0)∈ZN2b=-\operatorname{vec}(P_0A-BP_0)\in\mathbb{Z}^{N^2}. Writing the rectangular Smith normal form UM0(A,B)V=SUM_0(A,B)V=S with unimodular U∈GL⁡(N2,Z)U\in\operatorname{GL}(N^2,\mathbb{Z}) and V∈GL⁡((N−1)2,Z)V\in\operatorname{GL}((N-1)^2,\mathbb{Z}), the top (N−1)2(N-1)^2 rows give diag⁡(s1,…,smax⁡)(V−1z0)=(Ub)1:(N−1)2∈Z(N−1)2\operatorname{diag}(s_1,\ldots,s_{\max})(V^{-1}z_0)=(Ub)_{1:(N-1)^2}\in\mathbb{Z}^{(N-1)^2}. Since every sis_i divides smax⁡s_{\max} and VV is unimodular over Z\mathbb{Z}, it follows that smax⁡z0∈Z(N−1)2s_{\max}z_0\in\mathbb{Z}^{(N-1)^2}, and therefore ℓ∣smax⁡\ell\mid s_{\max}.

The Smith Normal Form and Subgraph Isomorphism

A natural question is how the Smith normal form might relate to the more general problem of subgraph isomorphism. Surprisingly, the formulation maps naturally so long as the problem is framed in the context of the symmetric lattice commutator

K(A,B)=LT(I⊗A−B⊗I)LK(A,B)=L^T(I\otimes A-B\otimes I)L

When M<NM<N, moving from square permutations P∈{0,1}N×NP\in\{0,1\}^{N\times N} to rectangular injections P∈{0,1}M×NP\in\{0,1\}^{M\times N} introduces two obstacles that are absent when M=NM=N:

  1. Asymmetric Column Sums Under Vertex Relabeling: When M=NM=N, every permutation matrix has column sums (1,1,…,1)(1,1,\ldots,1), which is invariant under any relabeling of GAG_A’s vertices. When M<NM<N, however, a rectangular injection P∈{0,1}M×NP\in\{0,1\}^{M\times N} matches MM columns of GAG_A (column sum 1) and leaves N−MN-M columns unmatched (column sum 0). Including a reference injection such as P0=[IM0M×(N−M)]P_0=\begin{bmatrix}I_M&0_{M\times(N-M)}\end{bmatrix} in the lattice basis would uniquely identify the first MM vertices of GAG_A, meaning that any relabeling of the vertices of GAG_A would permute the 1s and 0s across columns and alter the resulting Smith normal form.

  1. Boundary Edges Leaving the Subgraph: Even when GBG_B is an induced subgraph of GAG_A, edges in GAG_A connecting the MM matched vertices to the N−MN-M unmatched vertices create non-zero +1+1 entries in the unmatched columns of PA−BPPA-BP.

Both obstacles disappear if we consider differences between candidate injections rather than individual injection matrices.

If P1,P2∈{0,1}M×NP_1,P_2\in\{0,1\}^{M\times N} are any two rectangular injections mapping VBV_B onto the same MM-vertex subset of GAG_A, their difference matrix X=P1−P2X=P_1-P_2 exhibits two exact cancellations:

(i) Row sums vanish: Because each row of P1P_1 and P2P_2 sums to 1 (every vertex of GBG_B is mapped exactly once), every row of XX sums to 1−1=01-1=0, giving X1N=0MX\mathbf{1}_N=\mathbf{0}_M.

(ii) Column sums vanish universally: On the MM matched columns, both matrices have column sum 1, so 1−1=01-1=0. On the N−MN-M unmatched columns, neither matrix has any entries, so 0−0=00-0=0. Thus every column sum of XX is identically zero, giving XT1M=0NX^T\mathbf{1}_M=\mathbf{0}_N.

This motivates restricting our algebraic analysis to the zero-sum difference lattice:

LM,N(0)={X∈ZM×N:X1N=0M and XT1M=0N}.(16)\mathcal{L}_{M,N}^{(0)}=\left\{X\in\mathbb{Z}^{M\times N}:X\mathbf{1}_N=\mathbf{0}_M\ \text{and}\ X^T\mathbf{1}_M=\mathbf{0}_N\right\}. \tag*{(16)}

Working in LM,N(0)\mathcal{L}_{M,N}^{(0)} neatly eliminates both obstacles:

  • Subset and Relabeling Independence: Because every column sum in LM,N(0)\mathcal{L}^{(0)}_{M,N} is 00 regardless of which columns are matched or unmatched, LM,N(0)\mathcal{L}^{(0)}_{M,N} does not depend on which MM vertices of GAG_A are chosen. Permuting the vertices of GBG_B or GAG_A (X↦PBXPATX \mapsto P_B X P_A^{T}) simply permutes the rows and columns of XX, mapping LM,N(0)\mathcal{L}^{(0)}_{M,N} bijectively onto itself via a unimodular transformation in GL⁡(dM,N,Z)\operatorname{GL}(d_{M,N},\mathbb{Z}).

  • Boundary Edge Annihilation: Because the row and column sums of XX vanish identically, projecting the commutator operator onto LM,N(0)\mathcal{L}^{(0)}_{M,N} cancels the contributions of boundary edges exiting the subgraph, isolating the internal commutator structure of the induced copy.

Geometrically, LM,N(0)\mathcal{L}^{(0)}_{M,N} is the (M−1)(N−1)(M-1)(N-1)-dimensional lattice of integer swap moves (the tangent space of zero-sum perturbations to doubly-stochastic assignments), generated unimodularly by the (M−1)(N−1)(M-1)(N-1) elementary pairwise swap differences:

Ci,j=E1,1−E1,j−Ei,1+Ei,j∈{−1,0,1}M×N,2≤i≤M,2≤j≤N.(17)C_{i,j}=E_{1,1}-E_{1,j}-E_{i,1}+E_{i,j}\in\{-1,0,1\}^{M\times N},\qquad2\le i\le M,\quad2\le j\le N. \tag*{(17)}

Writing LM,N∈{−1,0,1}MN×(M−1)(N−1)L_{M,N}\in\{-1,0,1\}^{MN\times(M-1)(N-1)} for the matrix whose columns are vec⁡(Ci,j)\operatorname{vec}(C_{i,j}), define the projected commutator matrices:

K(A,B)=LM,NT(IM⊗A−B⊗IN)LM,N,K(B,B)=LM,MT(IM⊗B−B⊗IM)LM,M(18)K(A,B)=L_{M,N}^{T}(I_M\otimes A-B\otimes I_N)L_{M,N},\qquad K(B,B)=L_{M,M}^{T}(I_M\otimes B-B\otimes I_M)L_{M,M} \tag*{(18)}

of dimensions dM,N=(M−1)(N−1)d_{M,N}=(M-1)(N-1) and dM,M=(M−1)2d_{M,M}=(M-1)^2, separated by the dimension gap:

Δ=dM,N−dM,M=(M−1)(N−1)−(M−1)2=(N−M)(M−1).(19)\Delta=d_{M,N}-d_{M,M}=(M-1)(N-1)-(M-1)^2=(N-M)(M-1). \tag*{(19)}

Theorem 7 (SNF Interlacing for Induced Subgraphs). Let GAG_A (NN vertices) and GBG_B (M≤NM\le N vertices) be graphs with projected commutator matrices K(A,B)K(A,B) and K(B,B)K(B,B) as in Equation (18). Let

sBB=(sBB,1,…,sBB,dM,M)andsAB=(sAB,1,…,sAB,dM,N)s_{BB}=(s_{BB,1},\ldots,s_{BB,d_{M,M}})\qquad\text{and}\qquad s_{AB}=(s_{AB,1},\ldots,s_{AB,d_{M,N}})

denote the diagonal invariant factors of SNF⁡(K(B,B))\operatorname{SNF}(K(B,B)) and SNF⁡(K(A,B))\operatorname{SNF}(K(A,B)) ordered with non-zero divisors first (s1∣s2∣⋯∣srs_1\mid s_2\mid\cdots\mid s_r) followed by zeros.

If GB⊆indGAG_B\subseteq_{\mathrm{ind}}G_A, then for every 1≤i≤(M−1)21\le i\le(M-1)^2, the Smith normal form invariants satisfy the divisibility sandwich:

sAB,i∣sBB,i∣sAB,i+2(N−M)(M−1)(20)s_{AB,i}\mid s_{BB,i}\mid s_{AB,i+2(N-M)(M-1)} \tag*{(20)}

and the nullspace dimensions satisfy the lower bound:

dim⁡Null⁡(K(A,B))≥dim⁡Null⁡(K(B,B))−(N−M)(M−1).(21)\dim\operatorname{Null}(K(A,B))\ge\dim\operatorname{Null}(K(B,B))-(N-M)(M-1). \tag*{(21)}

Proof. Suppose GB⊆indGAG_B\subseteq_{\mathrm{ind}}G_A. By relabeling the vertices of GAG_A via a permutation matrix PA∈SNP_A\in S_N (which acts on LM,NL_{M,N} via a unimodular basis matrix U∈GL⁡(dM,N,Z)U\in\operatorname{GL}(d_{M,N},\mathbb{Z}) and leaves SNF⁡(K(A,B))\operatorname{SNF}(K(A,B)) invariant), we may place the induced copy of GBG_B on the first MM vertices of GAG_A:

PAAPAT=[BCCTD]P_AAP_A^{T}= \begin{bmatrix} B & C\\ C^{T} & D \end{bmatrix}

where C∈{0,1}M×(N−M)C\in\{0,1\}^{M\times(N-M)} encodes the boundary edges between GBG_B and VA∖VBV_A\setminus V_B. Partition the basis LM,N=[L~M,M  Lext]L_{M,N}=[\widetilde{L}_{M,M}\ \ L_{\mathrm{ext}}] into the dM,M=(M−1)2d_{M,M}=(M-1)^2 cycle matrices Ci,jC_{i,j} (2≤i,j≤M2\le i,j\le M) supported on the first MM columns—which are precisely the basis matrices of LM,ML_{M,M} padded with N−MN-M zero columns, X~=[X  0]\widetilde{X}=[X\ \ 0]—and the remaining Δ=(N−M)(M−1)\Delta=(N-M)(M-1) cycle matrices (M<j≤N)(M < j \le N). For any two padded matrices X~=[X0]\widetilde{X} = \begin{bmatrix} X & 0 \end{bmatrix} and Y~=[Y0]\widetilde{Y} = \begin{bmatrix} Y & 0 \end{bmatrix} in L~M,M\widetilde{L}_{M,M}, the commutator evaluates to:

X~[BCCTD]−BX~=[XB−BXXC].\widetilde{X}\begin{bmatrix} B & C \\ C^{T} & D \end{bmatrix} - B\widetilde{X} = \begin{bmatrix} XB-BX & XC \end{bmatrix}.

When we project against Y~\widetilde{Y} on the left, the N−MN-M zero columns of Y~=[Y0]\widetilde{Y} = \begin{bmatrix} Y & 0 \end{bmatrix} multiply the boundary block XCXC by zero, annihilating all boundary edges:

vec⁡(Y~)T(IM⊗PAAPAT−B⊗IN)vec⁡(X~)=tr⁡([YT0][XB−BXXC])=tr⁡(YT(XB−BX)).\operatorname{vec}(\widetilde{Y})^{T}(I_{M}\otimes P_{A}AP_{A}^{T}-B\otimes I_{N})\operatorname{vec}(\widetilde{X})=\operatorname{tr}\left(\begin{bmatrix}Y^{T} & 0\end{bmatrix}\begin{bmatrix}XB-BX & XC\end{bmatrix}\right)=\operatorname{tr}(Y^{T}(XB-BX)).

Thus the top-left dM,M×dM,Md_{M,M}\times d_{M,M} principal submatrix of UTK(A,B)UU^{T}K(A,B)U is identically K(B,B)K(B,B). Because K(B,B)K(B,B) is obtained from UTK(A,B)UU^{T}K(A,B)U by deleting Δ=(N−M)(M−1)\Delta=(N-M)(M-1) rows and Δ=(N−M)(M−1)\Delta=(N-M)(M-1) columns, the classical Smith normal form submatrix interlacing theorem [47] guarantees sAB,i∣sBB,i∣sAB,i+2Δs_{AB,i}\mid s_{BB,i}\mid s_{AB,i+2\Delta} for all 1≤i≤dM,M1\le i\le d_{M,M}, and Cauchy rank interlacing yields Equation (21).

Theorem 8 (SNF Interlacing for Non-Induced Subgraphs). Let GAG_{A} (NN vertices) and GBG_{B} (M≤NM\le N vertices) be graphs where every vertex of GBG_{B} has degree at least dd. If no two vertices of degree >d>d in GAG_{A} share an edge, then GB⊆GAG_{B}\subseteq G_{A} satisfies Equations (20) and Equation (21) of Theorem 7.

Proof. Suppose GB⊆GAG_{B}\subseteq G_{A}. Each matched vertex in GAG_{A} already uses at least dd edges to match the edges of GBG_{B}. Any extra edge in GAG_{A} between two matched vertices would increase both of their degrees in GAG_{A} to at least d+1>dd+1>d. Since no two vertices of degree >d>d in GAG_{A} share an edge, no such extra edge can exist, so GB⊆indGAG_{B}\subseteq_{\mathrm{ind}}G_{A} and Theorem 7 applies.

Example 1: Proving Planarity from the SNF

Since Theorem 7 is a necessary condition for subgraph embedding, refuting a forbidden pattern acts as a polynomial-time non-containment certificate. By Kuratowski’s theorem [48], a graph is planar if and only if it contains no subdivision of K5K_{5} or K3,3K_{3,3}, which is to say that rejecting K5K_{5} and K3,3K_{3,3} (along with candidate subdivisions on ≤N\le N vertices) via SNF interlacing immediately guarantees that the graph in question is planar.

By way of example, let the target graph be the 7-vertex planar Pentagonal Bipyramid GA=J13G_{A}=J_{13} (N=7N=7, ∣EA∣=15\lvert E_{A}\rvert=15, Figure 2a), formed by joining two polar hubs {1,2}\{1,2\} to an equatorial 5-cycle {3,4,5,6,7}\{3,4,5,6,7\}. Though a planar embedding exists, it is a classical visual example of a “difficult” toy example for planarity because the planar drawing is not visually obvious (Figure 2):

Inversion certificate on the N = 7 planar Pentagonal Bipyramid

Figure 2. Inversion certificate on the N=7N = 7 planar Pentagonal Bipyramid GA=J13G_A = J_{13} (∣EA∣=15|E_A| = 15): (a) the equatorial pentagon C5C_5 (M=5M = 5, blue) passes Theorem 7 with zero violations; (b) the Kuratowski clique K5K_5 (M=5M = 5) has universal signature sB′B′=[016]s_{B^{\prime}B^{\prime}} = [0^{16}] and is rejected via 0∤sAB′,17…240 \nmid s_{AB^{\prime},17\ldots24}; (c) the utility graph K3,3K_{3,3} (M=6M = 6) has universal signature sB′′B′′=[26,62,017]s_{B^{\prime\prime}B^{\prime\prime}} = [2^6,6^2,0^{17}] and is rejected via sB′′B′′,1…6=2∤sAB′′,11…16=1s_{B^{\prime\prime}B^{\prime\prime},1\ldots6} = 2 \nmid s_{AB^{\prime\prime},11\ldots16} = 1.

  • Case 1 (Kuratowski Clique GB′=K5⊈J13G_{B}^{\prime}=K_{5}\not\subseteq J_{13}, Refuted): Here M=5M=5, d5,5=16d_{5,5}=16, d5,7=24d_{5,7}=24, and 2Δ=162\Delta=16. Because K5K_{5} is a complete graph (so induced and non-induced containment coincide) and commutes with every 5×55\times5 permutation matrix, K(B′,B′)=0K(B^{\prime},B^{\prime})=0:

sB′B′=[0,0,0,0,0,0,0,0,0,…,0⏟i=1…8,0,…,0⏟i=9…16]s_{B^{\prime}B^{\prime}}=[0,0,0,0,0,0,0,0,\underbrace{0,\ldots,0}_{i=1\ldots8},\underbrace{0,\ldots,0}_{i=9\ldots16}]
sAB′=[1,…,1,1,1,5,5,45,45,45,45]s_{AB^{\prime}}=[1,\ldots,1,1,1,5,5,45,45,45,45]

At i=1,…,8i=1,\ldots,8, we have sB′B′,i=0s_{B^{\prime}B^{\prime},i}=0, whereas at i+16=17,…,24i+16=17,\ldots,24 we have sAB′,i+16∈{1,5,45}s_{AB^{\prime},i+16}\in\{1,5,45\}. Because 0∤10\nmid1, 0∤50\nmid5, and 0∤450\nmid45, Theorem 7 immediately refutes K5⊆J13K_{5}\subseteq J_{13} (and the nullity bound (21) also fails: 0<16−8=80<16-8=8). In fact, because KK5,K5=[016]K_{K_{5},K_{5}}=[0^{16}] universally, any NN-vertex graph containing K5K_{5} must satisfy dim⁡Null⁡(K(A,K5))≥16−4(N−5)\dim\operatorname{Null}(K(A,K_{5}))\ge16-4(N-5).

  • Case 2 (Utility graph GB′′=K3,3̸⊆indJ13G_{B^{\prime\prime}} = K_{3,3} \not\subseteq_{\mathrm{ind}} J_{13}, Refuted): Here M=6M = 6, d6,6=25d_{6,6} = 25, d6,7=30d_{6,7} = 30, Δ=(7−6)(6−1)=5\Delta= (7 - 6)(6 - 1) = 5, and the shift is 2Δ=102\Delta= 10:

sB′′B′′=[2,2,2,2,2,2,6,6,0,…,0,0,…,0]i=1…6i=9…1617…25(length 25)s_{B^{\prime\prime}B^{\prime\prime}} = [2,2,2,2,2,2,6,6,0,\ldots,0,0,\ldots,0] \quad\begin{array}{l} i=1\ldots6\\ i=9\ldots16\\ 17\ldots25 \end{array} \quad\text{(length 25)}
sAB′′=[1,…,1,1,1,1,1,1,1,1,2,2,2,2,2,6,24,24,120,600,0,…,0]1…10i+10=11…16i+10=19…2627…30(length 30)s_{AB^{\prime\prime}} = [1,\ldots,1,1,1,1,1,1,1,1,2,2,2,2,2,6,24,24,120,600,0,\ldots,0] \quad\begin{array}{l} 1\ldots10\\ i+10=11\ldots16\\ i+10=19\ldots26\\ 27\ldots30 \end{array} \quad\text{(length 30)}

At i=1,…,6i = 1,\ldots,6, we have sB′′B′′,i=2s_{B^{\prime\prime}B^{\prime\prime},i} = 2, whereas at i+10=11,…,16i + 10 = 11,\ldots,16 we have sAB′′,i+10=1s_{AB^{\prime\prime},i+10} = 1. Because 2∤12 \nmid1 (and at i=9,…,16i = 9,\ldots,16, 0∤sAB′′,19…260 \nmid s_{AB^{\prime\prime},19\ldots26}), Theorem 7 immediately refutes K3,3⊆indJ13K_{3,3} \subseteq_{\mathrm{ind}} J_{13} (and the nullity bound (21) also fails: 4<17−5=124 < 17 - 5 = 12).

Because we can guarantee that neither graph is present we have an immediate guarantee that the graph is planar without further investigation.

Example 2: Maximum Cycle Length Another classical existence problem in subgraph isomorphism is the determination of Hamiltonian (closed loop) cycles in a target graph. While the general problem is NP-complete, the SNF framing here allows quick certificates of non-existence of cycles of arbitrary size. Note that a negative result proves non-existence, while a positive result only allows for the possibility of existence, requiring further investigation to fully prove.

For example, let the target graph be the 2-connected, 7-vertex Theta-Bridge graph GAG_A (N=7N = 7, ∣EA∣=9|E_A| = 9, Figure 3a), formed by joining two degree-4 hubs {3,6}\{3,6\} via three paths of length 2 and one path of length 3. Because the only two vertices of degree >2> 2 are the non-adjacent hubs {3,6}\{3,6\}, Theorem 8 applies directly to every cycle CM⊆GAC_M \subseteq G_A, and testing the cycle ladder GB=C5,C6,C7G_B = C_5,C_6,C_7 determines the largest cycle that can possibly exist inside GAG_A a priori (Figure 3):

A priori maximum cycle bound via SNF: Probing $C_5 \to C_6 \to C_7$ on a 2-Connected $N=7$ Graph

Figure 3. A priori maximum cycle bound via K(A,B)=LM,NT(IM⊗A−B⊗IN)LM,NK(A,B)=L_{M,N}^{T}(I_M\otimes A-B\otimes I_N)L_{M,N} on a 2-connected N=7N=7 host graph GAG_A (deg =[2,2,2,2,2,4,4]=[2,2,2,2,2,4,4], ∣EA∣=9|E_A|=9): (a) GAG_A with its longest cycle C5C_5 highlighted in green; (b) GB=C5G_B=C_5 (M=5M=5, 2Δ=162\Delta=16) passes Theorem 7 with zero violations; (c) GB′=C6G_{B'}=C_6 (M=6M=6, 2Δ=102\Delta=10) is rejected via sB′B′,9..10=2∤1s_{B'B',9..10}=2\nmid1 and sB′B′,11..13=6∤1,3s_{B'B',11..13}=6\nmid1,3; (d) GB′′=C7G_{B''}=C_7 (M=7M=7, 2Δ=02\Delta=0) is rejected via sB′′B′′,17..24=7∤1s_{B''B'',17..24}=7\nmid1 and 0∤sAB′′,25..360\nmid s_{AB'',25..36}, establishing M∗=5M^*=5 as the maximum possible cycle length.

  • Case 1 (5-Cycle GB=C5⊆indGAG_B = C_5 \subseteq_{\mathrm{ind}} G_A, Passes): Here M=5M = 5, d5,5=16d_{5,5} = 16, d5,7=24d_{5,7} = 24, Δ=8\Delta= 8,

and the shift is 2Δ=162\Delta= 16:

sBB=[1,1,1,1,5,5,5,5,0,…,0](length 16)s_{BB} = [1,1,1,1,5,5,5,5,0,\ldots,0] \quad\text{(length 16)}
sAB=[1,…,1,5,5,5,10,10,10,10,0,0,0,0](length 24)s_{AB} = [1,\ldots,1,5,5,5,10,10,10,10,0,0,0,0] \quad\text{(length 24)}

For i=1,…,4i = 1,\ldots,4, sAB,i=1∣sBB,i=1∣sAB,i+16=10s_{AB,i} = 1 \mid s_{BB,i} = 1 \mid s_{AB,i+16} = 10, and for i=5,…,8i = 5,\ldots,8, sBB,i=5∣sAB,i+16=0s_{BB,i} = 5 \mid s_{AB,i+16} = 0. The nullity bound (21) also holds (4≥8−8=04 \ge8-8 = 0), matching the green 5-cycle (3–5–6–7–4–3) in Figure 3a. The possibility of a C5C_5 has not been rejected.

  • Case 2 (6-Cycle GB′=C6̸⊆indGAG_{B'} = C_6 \not\subseteq_{\mathrm{ind}} G_A, Refuted): Here M=6M = 6, d6,6=25d_{6,6} = 25, d6,7=30d_{6,7} = 30, Δ=5\Delta= 5, and the shift is 2Δ=102\Delta= 10:

sB′B′=[1,…,1,2,2,6,6,6,6,6,6,0,…,0](length 25)s_{B'B'} = [1,\ldots,1,2,2,6,6,6,6,6,6,0,\ldots,0] \quad\text{(length 25)}
sAB′=[1,…,1,1,1,1,1,3,3,6,6,6,6,228,2052](length 30)s_{AB'} = [1,\ldots,1,1,1,1,1,3,3,6,6,6,6,228,2052] \quad\text{(length 30)}

At i=9,10i = 9,10, we have sB′B′,i=2s_{B'B',i} = 2, whereas at i+10=19,20i + 10 = 19,20 we have sAB′,i+10=1s_{AB',i+10} = 1. At i=11,12,13i = 11,12,13, we have sB′B′,i=6s_{B'B',i} = 6, whereas at i+10=21,22,23i + 10 = 21,22,23 we have sAB′,i+10∈{1,3}s_{AB',i+10} \in\{1,3\}. Because 2∤12 \nmid1, 6∤16 \nmid1, and 6∤36 \nmid3, Theorem 7 immediately refutes C6⊆indGAC_6 \subseteq_{\mathrm{ind}} G_A (and the nullity bound (21) also fails: 0<9−5=40 < 9 - 5 = 4).

  • Case 3 (7-Cycle GB′′=C7̸⊆indGAG_{B''} = C_7 \not\subseteq_{\mathrm{ind}} G_A, Refuted): Here M=N=7M = N = 7, d7,7=36d_{7,7} = 36, Δ=(7−7)(7−1)=0\Delta= (7 - 7)(7 - 1) = 0, and the shift is 2Δ=02\Delta= 0:

sB′′B′′=[1,…,1,7,7,7,7,7,7,7,7,0,…,0](length 36)s_{B''B''} = [1,\ldots,1,7,7,7,7,7,7,7,7,0,\ldots,0] \quad\text{(length 36)}
sAB′′=[1,…,1,1,1,1,1,1,1,1,1,1,14,76,21492](length 36)s_{AB''} = [1,\ldots,1,1,1,1,1,1,1,1,1,1,1^{4},7^{6},2149^{2}] \quad\text{(length 36)}

At i=17,…,24i = 17,\ldots,24, we have sB′′B′′,i=7s_{B''B'',i} = 7, whereas at i+0=17,…,24i + 0 = 17,\ldots,24 we have sAB′′,i=1s_{AB'',i} = 1. Because 7∤17 \nmid1 (and at i=25,…,36i = 25,\ldots,36, 0∤sAB′′,i0 \nmid s_{AB'',i} with nullity 0<120 < 12), Theorem 7 immediately refutes C7⊆indGAC_7 \subseteq_{\mathrm{ind}} G_A (and restricting to the five zero-slack degree-2 vertices similarly rules out chorded C7C_7). Together, Cases 1–3 certify a priori that C5C_5 (M∗=5M^* = 5) is the largest possible cycle in GAG_A.

Driving Case Study: The Algebraic Anatomy of the Knight's Tour

We close the theoretical portion of the paper with an application of the principles developed in § 2–§ 4.1 to the familiar Knight’s Tour problem. A classic benchmark in introductory computer science and combinatorial optimization [49, 50, 51, 52], it asks whether a knight can visit every square of an R×CR \times C (or punctured “Swiss-Cheese”) chessboard exactly once and, potentially by extension, return to its starting square.

In our algebraic framework, the host graph GAG_A on an R×CR \times C board has a natural Kronecker structure: every knight jump combines a stride-1 shift J1J_1 along one axis with a stride-2 shift J2J_2 along the perpendicular axis, so the full board adjacency matrix is the sum of two Kronecker outer products:

A=(J2(R)⊗J1(C))+(J1(R)⊗J2(C)).(22)A = \left(J_2^{(R)} \otimes J_1^{(C)}\right) + \left(J_1^{(R)} \otimes J_2^{(C)}\right). \tag*{(22)}

Finding a closed MM-step tour inside an NN-square active board (M≤NM \le N) is the subgraph isomorphism problem for the cycle GB=CMG_B = C_M. This setting provides a visual, end-to-end demonstration of how our three tools interact:

  1. SNF Subgraph Interlacing (M≤NM\le N, Theorem 7): Certifying the maximum possible closed sub-tour CMC_M on small boards directly from the invariant factors of K(A,B)=LM,NT(IM⊗A−B⊗IN)LM,NK(A,B)=L_{M,N}^{T}(I_M\otimes A-B\otimes I_N)L_{M,N} (§ 6.1).

  1. Degree-2 Edge Pruning & Torsion Sieving (M=NM=N): Taking advantage of the fact that degree-2 nodes must use both incident edges in any 2-regular cycle, eliminating dead chords saturated by degree-2 border/corner squares and refuting parity-trapped boards.

  1. Global Commutator ILP / CP-SAT (Equation (5)): Resolving board-wide flow bottlenecks on punctured Swiss-Cheese boards where local backtracking and arc-consistency solvers time out (§ 7.1).

Worked Example (N=12N=12): Why the 3×43\times4 Chessboard Has a 10-Cycle But No Closed Tour

A classic puzzle asks why the 3×43\times4 chessboard (N=12N=12 squares, ∣EA∣=14|E_A|=14 knight moves) admits an open Knight’s Tour (P12P_{12}), yet admits no closed Knight’s Tour (C12C_{12}), and what the longest closed tour on the board actually is. Because the 3×43\times4 board is bipartite (6 White and 6 Black squares), any closed cycle must have even length M∈{6,8,10,12}M\in\{6,8,10,12\}. Probing GB=C10G_B=C_{10} and GB′=C12G_{B'}=C_{12} via K(A,B)=LM,NT(IM⊗A−B⊗IN)LM,NK(A,B)=L_{M,N}^{T}(I_M\otimes A-B\otimes I_N)L_{M,N} certifies a priori why no closed 12-cycle exists while permitting the 10-step closed tour shown in Figure 4a:

SNF cycle sieve on the classic 3 × 4 chessboard

Figure 4. SNF cycle sieve on the classic 3×43 \times4 chessboard (N=12N = 12, ∣EA∣=14|E_A| = 14): (a) the closed 10-step sub-tour C10C_{10} (M=10M = 10, green, omitting middle-edge squares 5 and 8) passes Theorem 7 with zero violations; (b) the full 12-step cycle C12C_{12} (M=12M = 12) is rejected on raw AA via 2∤12 \nmid1 and 12∤1,212 \nmid1, 2; (c) pruning the two red dashed chords saturated by the eight degree-2 squares splits A~≅C6⊔C6\widetilde{A} \cong C_6 \sqcup C_6 into two disjoint 6-cycles (orange and blue), whose 6-cycle torsion (sA~B′,83..87∈{2,4}s_{\widetilde{A}B',83..87} \in\{2, 4\}) fails 12∣sA~B′,i12 \mid s_{\widetilde{A}B',i} and certifies M∗=10M^* = 10 as the longest closed tour.

  • Case 1 (Closed 10-Step Sub-Tour GB=C10⊆indG3×4G_B=C_{10}\subseteq_{\mathrm{ind}}G_{3\times4}, Passes): Here M=10M=10, d10,10=81d_{10,10}=81, d10,12=99d_{10,12}=99, Δ=(12−10)(10−1)=18\Delta=(12-10)(10-1)=18, and the shift is 2Δ=362\Delta=36:

sBB=[1,…,1, 2,2, 10,…,10, 0,…,0]s_{BB}=[1,\ldots,1,\ 2,2,\ 10,\ldots,10,\ 0,\ldots,0]

(length 81)

sAB=[1,…,1, 27, 10, 204, 20, 20, 203, 220, 1320, 0,…,0]s_{AB}=[1,\ldots,1,\ 2^7,\ 10,\ 20^4,\ 20,\ 20,\ 20^3,\ 220,\ 1320,\ 0,\ldots,0]

(length 99)

For i=1,…,48i=1,\ldots,48, sBB,i=1∣sAB,i+36s_{BB,i}=1\mid s_{AB,i+36}; for i=49,50i=49,50, sBB,i=2∣sAB,85..86=20s_{BB,i}=2\mid s_{AB,85..86}=20; for i=51,…,63i=51,\ldots,63, sBB,i=10s_{BB,i}=10 divides sAB,87..91∈{20,220,1320}s_{AB,87..91}\in\{20,220,1320\} and sAB,92..99=0s_{AB,92..99}=0 (while for i≥64i \ge64, i+36>99i+36 > 99). All 81 divisibility checks pass with zero violations, matching the green 10-step closed tour in Figure 4a (which omits the two middle-edge squares 5 and 8).

  • Case 2 (Full 12-Step Tour GB′=C12⊈G3×4G_{B'} = C_{12} \not\subseteq G_{3\times4} on Raw AA, Refuted): Here M=N=12M=N=12, d12,12=121d_{12,12}=121, Δ=0\Delta=0, and the shift is 2Δ=02\Delta=0:

sB′B′=[1,…,1, 2,2, 12,…,12, 0,…,0](length 121)s_{B'B'} = [1,\ldots,1,\ 2,2,\ 12,\ldots,12,\ 0,\ldots,0]\quad\text{(length 121)}
sAB′=[1,…,1, 1,1, 114,24, 47, 1211,1202,240](length 121)s_{AB'} = [1,\ldots,1,\ 1,1,\ 1^{14},2^{4},\ 4^{7},\ 12^{11},120^{2},240]\quad\text{(length 121)}

At i=81,82i=81,82, we have sB′B′,i=2∤sAB′,i=1s_{B'B',i}=2\nmid s_{AB',i}=1, and at i=83,…,100i=83,\ldots,100, we have sB′B′,i=12∤sAB′,i∈{1,2}s_{B'B',i}=12\nmid s_{AB',i}\in\{1,2\} (41 total violations; nullity 0<210<21).

  • Case 3 (Full 12-Step Tour GB′=C12⊈G3×4G_{B'} = C_{12} \not\subseteq G_{3\times4} on Degree-2 Pruned A~\widetilde{A}, Refuted): What if a 12-cycle used the two extra edges of G3×4G_{3\times4} (∣EA∣=14>12|E_A|=14>12) as chords? On the 3×43\times4 board, eight squares {1,4,5,6,7,8,9,12}\{1,4,5,6,7,8,9,12\} have degree 2, so any 12-cycle must use both incident edges of all eight squares. This saturates the four remaining degree-3 squares {2,3,10,11}\{2,3,10,11\} and forces the two cross-chords (2,11)(2,11) and (3,10)(3,10) to be unused (red dashed lines in Figure 4c). Deleting those two dead chords yields a 2-regular graph A~\widetilde{A} (∣EA~∣=12|E_{\widetilde{A}}|=12) on which any 12-cycle would have zero slack (PA~−C12P=0P\widetilde{A}-C_{12}P=0). Yet K(A~,C12)K(\widetilde{A},C_{12}) still fails Theorem 7:

sB′B′=[1,…,1, 2,2, 12,12,12,12,12, 12,…,12, 0,0,0, 0,…,0]s_{B'B'}=[1,\ldots,1,\ 2,2,\ 12,12,12,12,12,\ 12,\ldots,12,\ 0,0,0,\ 0,\ldots,0]
sAB~′=[1,…,1, 2,2, 2,2,4,4,4, 12,…,12, 24,24,48, 0,…,0]s_{A\widetilde{B}'}=[1,\ldots,1,\ 2,2,\ 2,2,4,4,4,\ 12,\ldots,12,\ 24,24,48,\ 0,\ldots,0]

At i=83,…,87i=83,\ldots,87, sB′B′,i=12s_{B'B',i}=12 whereas sAB~′,i∈{2,4}s_{A\widetilde{B}',i}\in\{2,4\} (12∤212\nmid2 and 12∤412\nmid4), and the nullity drops from 21 to 18. Geometrically, pruning the two saturated chords splits the 3×43\times4 board into two disjoint 6-cycles (A~≅C6⊔C6\widetilde{A}\cong C_6\sqcup C_6, orange and blue in Figure 4c), replacing 12-cycle torsion with 6-cycle torsion and proving that M∗=10M^*=10 is the maximum closed Knight’s Tour on a 3×43\times4 board.

CP-SAT, Integer Linear Programming, and Applied SGI

We end the paper with a rigorously applied measurement of the performance of these tools on known benchmarks, as well as some combinatorially difficult “Swiss-Cheese” Knight’s Tour boards that show the challenges in various subgraph search strategies. We find that the superexponential nature of many of these problems becomes immediately obvious, with problems either solved near instantly, or timing out after six hours of runtime. We show that using simple off-the-shelf libraries and a consumer desktop, the algorithms above solve all problems presented in 6 seconds or less, compared to more typical 6-hour timeouts for all alternatives tested. Moreover, the algorithms themselves are easily represented in a few readable lines of Python, making use and distribution efficient and easy.

Specifically, the Kronecker commutator inequalities of Equation (5) translate directly into a compact 0–1 integer linear program / CP-SAT model [53] over the MNMN binary decision variables P∈{0,1}M×NP\in\{0,1\}^{M\times N}:

P1N=1M,PT1M≤1N,0≤(IM⊗A−B⊗IN)vec⁡(P)≤1(23)P\mathbf{1}_N=\mathbf{1}_M,\qquad P^T\mathbf{1}_M\le\mathbf{1}_N,\qquad0\le(I_M\otimes A-B\otimes I_N)\operatorname{vec}(P)\le1 \tag*{(23)}

together with the complement constraint 0≤(IM⊗A‾−B‾⊗IN)vec⁡(P)≤10\le(I_M\otimes\overline{A}-\overline{B}\otimes I_N)\operatorname{vec}(P)\le1 when solving for induced subgraphs. In all benchmarks below, our solver (Commutator SGI) passes this base k=1k = 1 linear system directly to off-the-shelf OR-Tools CP-SAT (8 worker threads on an AMD EPYC workstation), without requiring the lattice coordinate change LL of § 4.1 or higher-order walk inequalities (k≥2k \ge2).

The Swiss-Cheese Knight’s Tour Showdown (8 × 8, 10 × 10, and 12 × 12)

Scaling up to 8×88 \times8, 10×1010 \times10, and 12×1212 \times12 chessboards with balanced White/Black punctures (∣W∣=∣B∣|W| = |B|), we benchmarked seven algorithms across 12 hard Swiss-Cheese instances (mixing feasible tours with subtle parity and degree-2 bottleneck traps): the Warnsdorff + Pohl Multi-Start Heuristic [49, 50] (launched from all NN starting squares), Warnsdorff + Pohl Exact Backtracking, four canonical C/C++ subgraph isomorphism solvers (C++ Glasgow, C++ FASTiso, C-LAD, C-VF2), and our Commutator SGI solver [5]. Results are shown in Table 1 and Figure 5–Figure 6.

Swiss-Cheese Board InstanceW+P Heur (All NN Starts)W+P Exact (Backtrack)C++ GlasgowC++ FASTisoC-LAD (Solnon)C-VF2 (Foggia)Commutator SGI [Ours]
KT1. 8×88 \times8 Closed Tour (10 Holes, SAT)FAIL (0/54)TIMEOUT (> 21600s)TIMEOUT (> 21600s)True (4.30s)True (0.02s)TIMEOUT (> 21600s)True (0.48s)
KT2. 8×88 \times8 Closed Tour (8 Holes, UNSAT)FAIL (0/56)TIMEOUT (> 21600s)False (0.01s)TIMEOUT (> 21600s)False (0.00s)TIMEOUT (> 21600s)False (0.07s)
KT3. 8×88 \times8 Open Path (10 Holes, SAT)True (0.00s)True (0.10s)TIMEOUT (> 21600s)True (5492.04s)True (0.01s)True (9304.52s)True (3.62s)
KT4. 8×88 \times8 Trap (10 Holes, 27W=27B27W = 27B)FAIL (0/54)TIMEOUT (> 21600s)False (0.00s)TIMEOUT (> 21600s)False (0.00s)TIMEOUT (> 21600s)False (0.06s)
KT5. 8×88 \times8 Closed Tour (12 Holes, Hard SAT)FAIL (0/52)True (72.05s)TIMEOUT (> 21600s)True (10.83s)True (0.01s)TIMEOUT (> 21600s)True (0.33s)
KT6. 8×88 \times8 Trap (14 Holes, 25W=25B25W = 25B)FAIL (0/50)False (0.00s)False (0.01s)TIMEOUT (> 21600s)False (0.00s)TIMEOUT (> 21600s)False (0.08s)
KT7. 10×1010 \times10 Trap (20 Holes, 40W=40B40W = 40B)FAIL (0/80)TIMEOUT (> 21600s)False (0.01s)TIMEOUT (> 21600s)False (0.00s)TIMEOUT (> 21600s)False (0.27s)
KT8. 10×1010 \times10 Trap (16 Holes, 42W=42B42W = 42B)FAIL (0/84)FAIL (0/84)False (0.01s)TIMEOUT (> 21600s)False (0.00s)TIMEOUT (> 21600s)False (0.29s)
KT9. 10×1010 \times10 Trap (20 Holes, 40W=40B40W = 40B)FAIL (0/80)TIMEOUT (> 21600s)TIMEOUT (> 21600s)TIMEOUT (> 21600s)False (0.06s)TIMEOUT (> 21600s)False (0.69s)
KT10. 10×1010 \times10 Trap (20 Holes, 40W=40B40W = 40B)FAIL (0/80)TIMEOUT (> 21600s)TIMEOUT (> 21600s)TIMEOUT (> 21600s)False (0.00s)TIMEOUT (> 21600s)False (0.85s)
KT11. 12×1212 \times12 Trap (24 Holes, 60W=60B60W = 60B)FAIL (0/120)TIMEOUT (> 21600s)False (0.01s)TIMEOUT (> 21600s)False (0.00s)TIMEOUT (> 21600s)False (0.80s)
KT12. 12×1212 \times12 Trap (26 Holes, 60W=60B60W = 60B)FAIL (0/120)TIMEOUT (> 21600s)False (0.01s)TIMEOUT (> 21600s)False (0.00s)TIMEOUT (> 21600s)False (0.78s)
Summary: Solved / 12 (Timeouts)1/123/12 (9 TO)7/12 (5 TO)3/12 (9 TO)10/12 (2 TO)1/12 (11 TO)12/12 (0 Timeouts)

Table 1. Swiss-Cheese Hamiltonian Knight’s Tour Showdown Across 7 Solvers (21,600 s / 6-Hour Timeout Ceiling).

Per-instance runtime and cactus/survival profile for Swiss-Cheese Hamiltonian Knight’s Tour boards

Figure 5. Swiss-Cheese Hamiltonian Knight’s Tour Showdown (1,000 s timeout ceiling): (a) Per-instance log-scale runtime across 12 punctured 8×88 \times8, 10×1010 \times10, and 12×1212 \times12 boards (solid bars = solved; hatched bars = timeout at 1,000 s); (b) Cumulative survival / cactus profile from 10−410^{-4} s to 1,000 s across all 7 solvers.

Three-panel visual gallery of Swiss-Cheese Knight’s Tour graphs

Figure 6. Three-Panel Visual Gallery of Swiss-Cheese Knight’s Tour Graphs: (a) 8×88 \times8 Closed Hamiltonian Tour on Seed 84 (N=54N = 54, solved in 0.48s where Warnsdorff+Pohl fails 54/54 starts); (b) 8×88 \times8 Closed Hamiltonian Tour on Seed 29 (12 Holes, N=52N = 52, solved in 0.33s where Glasgow, FASTiso, VF2 & Warnsdorff Backtracking all either timeout or take > 10s); (c) 10×1010 \times10 Balanced Parity Trap on Seed 48 (40W=40B40\mathrm{W} = 40\mathrm{B}, UNSAT refuted in 0.83s, highlighting the forced degree-2 corridors that prevent a global cycle).

Why Subgraph Backtracking Solvers Struggle on CNC_N (and How Global Commutator LP & Degree-2 Pruning Resolve It)

At first glance, it may seem surprising that state-of-the-art subgraph solvers such as Glasgow, FASTiso, and VF2 time out at 1,000 s on 52-to-80 vertex graphs that our CP-SAT commutator formulation solves in under a second. The reason is structural: combinatorial SGI solvers

rely primarily on vertex-degree and neighborhood-sequence filtering to prune candidate domains before branching. When the pattern graph is a uniform 2-regular cycle GB=CNG_B = C_N, every pattern vertex has identical degree 2 and identical kk-step neighborhood profiles, so every target square with deg⁡A(v)≥2\deg_A(v) \ge2 remains a valid candidate for every pattern vertex. Without conflict-driven clause learning (CDCL) or a global linear programming relaxation, backtracking search degenerates into exploring symmetric cycle permutations, whereas C-LAD [10] either finishes in ≤0.02\le0.02 s via root-level Hall filtering or times out completely at >1,000> 1,000 s:

  • Easy Local Traps (KT2, KT4, KT6, KT8, KT9, KT11, KT12): On these seven UNSAT boards, the punctured board leaves at least one square with deg⁡A(v)≤1\deg_A(v) \le1 or a direct local Hall marriage violation. Root-level degree and Hopcroft–Karp filtering detects the dead end in ≤0.01\le0.01 s without branching.

  • Hard Degree-≥2\ge2 Bottleneck Traps (KT7 Seed 48 and KT10 Seed 73): On KT7 (Figure 6c) and KT10, the board is connected, bipartite-balanced (40W=40B40\mathrm{W} = 40\mathrm{B}), every single square has deg⁡A(v)≥2\deg_A(v) \ge2, and the 40×4040 \times40 White-to-Black biadjacency matrix MbipM_{\mathrm{bip}} has full rank (rank⁡(Mbip)=40\operatorname{rank}(M_{\mathrm{bip}}) = 40), so 1-factors exist and local Hall propagation prunes zero branches—causing C-LAD, Glasgow, FASTiso, VF2, and Warnsdorff Backtracking to all time out at >1,000> 1,000 s.

  • Degree-2 Pruning & Global Commutator Resolution: Why are KT7 and KT10 infeasible? Inspecting their degree-2 neighborhoods reveals the exact obstruction: after one step of degree-2 edge pruning (A~\widetilde{A}), both boards contain a hub square adjacent to three degree-2 squares (max⁡u(A~1V2)u=3\max_u(\widetilde{A}_1 V_2)_u = 3). Because three forced degree-2 edges converging on a single vertex cannot be accommodated by a 2-regular cycle (3c=2c⇒c=03c = 2c \Rightarrow c = 0, so 1dTV0=0\mathbf{1}_d^{\mathsf{T}}V_0 = 0), both boards are certified UNSAT in <2< 2 ms (and even without running the pre-sieve, the global LP relaxation and CDCL engine of our base CP-SAT commutator program (23) resolve the same flow contradiction in 0.83 s and 0.89 s, achieving 12/12 completion with zero timeouts).

General SGI Benchmarks

Master Benchmark Across Four Challenge Regimes

To evaluate how the rectangular commutator formulation performs across general subgraph isomorphism regimes (M≤NM \le N), Table 2 summarizes head-to-head runtime performance against the four canonical C/C++ solvers (Glasgow [11, 12], FASTiso [9], C-LAD [10], and C-VF2 [6]) across CNRS/LIRIS hard benchmark instances (LV/g24 [54]), regular combinatorial crossover graphs, Swiss-Cheese Knight’s Tours, and IBM Heavy-Hex quantum layouts.

Benchmark Suite & InstanceC++ Glasgow (McCreesh)C++ FASTiso (Agapito et al.)C-LAD (Sothin)C-VF2 (Foggia)Commutator SGI (Ours)
A1. CNRS LV/g24-g29 (75 × 100, UNSAT)TIMEOUT (> 21600s)False (0.06 s)TIMEOUT (> 21600s)TIMEOUT (> 21600s)False (3.32 s)
A2. CNRS LV/g24-g30 (75 × 100, UNSAT)TIMEOUT (> 21600s)False (0.06 s)TIMEOUT (> 21600s)TIMEOUT (> 21600s)False (3.56 s)
A3. CNRS LV/g24-g31 (75 × 100, UNSAT)TIMEOUT (> 21600s)False (0.11 s)TIMEOUT (> 21600s)TIMEOUT (> 21600s)False (4.06 s)
A4. CNRS LV/g24-g45 (75 × 128, UNSAT)False (0.02 s)False (0.03 s)TIMEOUT (> 21600s)TIMEOUT (> 21600s)False (4.73 s)
A5. CNRS LV/g24-g47 (75 × 128, UNSAT)False (0.02 s)False (0.03 s)TIMEOUT (> 21600s)TIMEOUT (> 21600s)False (4.39 s)
A6. MIVIA sis_b2-200 (40 × 200, SAT)True (0.01 s)True (0.01 s)True (0.02 s)True (0.00 s)True (0.32 s)
A7. BioModels 071-153 (39 × 227, UNSAT)False (0.01 s)False (0.01 s)False (0.00 s)False (71.54 s)False (0.11 s)
A8. Phase-Trans 30=150-0-34 (30 × 150, SAT)True (0.03 s)True (0.01 s)True (0.11 s)True (89.49 s)True (5.43 s)
B1. Disjoint 3-Reg K=8K = 8 (N=80N = 80, UNSAT)False (0.01 s)False (0.61 s)False (31.72 s)False (3.88 s)False (0.88 s)
B2. Disjoint 3-Reg K=9K = 9 (N=90N = 90, UNSAT)False (0.01 s)False (4.34 s)False (253.80 s)False (28.45 s)False (1.34 s)
B3. Disjoint 3-Reg K=10K = 10 (N=100N = 100, UNSAT)False (0.01 s)False (25.62 s)False (3221.78 s)False (228.07 s)False (1.89 s)
B4. Disjoint (8,3)-Reg 6-Pairs (N=96N = 96, UNSAT)False (0.01 s)TIMEOUT (> 21600s)TIMEOUT (> 21600s)TIMEOUT (> 21600s)False (1.99 s)
C1. Knight’s Tour 8 × 8 (10 Holes, SAT)TIMEOUT (> 21600s)True (4.30 s)True (0.02 s)True (27.88 s)True (0.48 s)
D1. Quantum Heavy-Hex (M=18M = 18 in N=27N = 27, SAT)True (0.01 s)True (0.00 s)True (0.00 s)True (0.00 s)True (0.13 s)
Summary: Solved / Total (Timeouts)10/15 (5 TO)13/15 (2 TO)8/15 (7 TO)7/15 (8 TO)15/15 (0 Timeouts)

Table 2. Master Head-to-Head Runtime Comparison Across 5 Canonical Solvers (1,000 s Timeout).

Across an expanded 25-instance multi-regime benchmark suite (21,600 s / 6-hour timeout ceiling; Figure 7), Commutator SGI is the only solver to achieve 100% completion (25/25 solved in ≤5.32\le5.32 s, 0 timeouts) with a mean solve time of 1.04 s, compared to C++ FASTiso (18/25, 72%), C++ Glasgow (18/25, 72%), C-LAD (18/25, 72%), and C-VF2 (11/25, 44%). Even with a generous 6-hour runtime budget per instance, the combinatorial backtracking engines struggle on global parity and topological density traps.

Multi-Regime SGI Benchmark Survival / Cactus Profile

Figure 7. Multi-Regime SGI Benchmark Survival / Cactus Profile (21,600 s / 6-hour timeout ceiling) across 25 instances comparing Official C++ Glasgow, Official C++ FASTiso, Official C-LAD, Official C-VF2, and Commutator SGI (Ours).

Conclusion

We presented a simple linear framing for graph and subgraph isomorphism, shown most elegantly in the base equations

(I⊗A−B⊗I)⋅vec⁡(P)=0(I \otimes A - B \otimes I) \cdot\operatorname{vec}(P) = 0
0≤(IM⊗A−B⊗IN)⋅vec⁡(P)≤10 \le(I_{M} \otimes A - B \otimes I_{N}) \cdot\operatorname{vec}(P) \le1

for GI and SGI respectively.

The linear commutator framework provides a clean, unified bridge between algebraic graph theory, discrete lattices, and modern mathematical programming. In addition to offering new directions for theoretical investigation, it also offers a very direct set of methods for quickly resolving graph questions using scalable modern hardware and software via off-the-shelf libraries. Moreover, given the connection to CP-SAT and ILP, it is easy to extend additional constraints or other a priori knowledge to applied SGI without additional overhead or special-purpose software.

The connection to lattices and the Smith normal form was shown to have a rich connection to deep SGI problems of planarity and Hamiltonian cycles that only scratches the surface of what might be possible to prove about general graph properties. We also showed the direct connection between any graph isomorphism problem and the NP-complete shortest and closest vector problems [55, 56].

Finally, we demonstrated a clean, fast implementation of the Knight’s Tour that is easily implemented and functions as a readable entry point for students and researchers looking to demonstrate these principles at scale.

References

  1. [1]Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
  2. [2]Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II. Journal of Symbolic Computation, 60:94–112, 2014.
  3. [3]László Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 684–697. ACM, 2016.arxiv.org/abs/1512.03547
  4. [4]Martin Grohe and Pascal Schweitzer. The graph isomorphism problem. Communications of the ACM, 63(11):128–134, 2020.DOI
  5. [5]Julian R. Ullmann. An algorithm for subgraph isomorphism. Journal of the ACM, 23(1):31–42, 1976.DOI
  6. [6]Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. A (sub)graph isomorphism algorithm for matching large graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(10):1367–1372, 2004.pubmed.ncbi.nlm.nih.gov/15641723
  7. [7]Vincenzo Bonnici, Rosalba Giugno, Alfredo Pulvirenti, Dennis Shasha, and Alfredo Ferro. A subgraph isomorphism algorithm and its application to biochemical data. BMC Bioinformatics, 14(Suppl 7):S13, 2013.DOI
  8. [8]Vincenzo Carletti, Pasquale Foggia, Alessia Saggese, and Mario Vento. Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with VF3. IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(4):804–818, 2018.DOI
  9. [9]Wilfried Agbeto, Camille Coti, and Vladimir Reinharz. FASTiso: Fast algorithm on search state tree for subgraph isomorphism in graphs of any size and density. bioRxiv, 2025. Available at https://gitlab.info.uqam.ca/cbe/fastiso.
  10. [10]Christine Solnon. AllDifferent-based filtering for subgraph isomorphism. Artificial Intelligence, 174(12-13):850–864, 2010.DOI
  11. [11]Ciaran McCreesh and Patrick Prosser. The shape of the search tree for the maximum clique problem and the implications for parallel branch and bound. ACM Transactions on Parallel Computing (TOPC), 2(1):1–27, 2015.arxiv.org/abs/1401.5921
  12. [12]Ciaran McCreesh, Patrick Prosser, and James Trimble. The Glasgow subgraph solver: Using constraint programming to tackle hard subgraph isomorphism problem variants. In International Conference on Graph Transformation (ICGT), volume 12150 of Lecture Notes in Computer Science, pages 316–324. Springer, 2020.DOI
  13. [13]Stephan Gocht, Ciaran McCreesh, and Jakob Nordström. Subgraph isomorphism meets cutting planes: Solving with certified solutions. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI), pages 1134–1140. International Joint Conferences on Artificial Intelligence Organization, 2020.DOI
  14. [14]Wook-Shin Han, Jinsoo Lee, and Jeong-Hoon Lee. TurboISO: Towards ultrafast and robust subgraph isomorphism search in large graph databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 337–348, 2013.DOI
  15. [15]Myoungji Han, Hyunjoon Kim, Geonmo Gu, Kunsoo Park, and Wook-Shin Han. Efficient subgraph matching: Harmonizing dynamic programming, adaptive matching order, and failing set together. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 1429–1446, 2019.
  16. [16]Chris Godsil and Gordon Royle. Algebraic Graph Theory, volume 207 of Graduate Texts in Mathematics. Springer, 2001.DOI
  17. [17]Wei Wang and Cheng-Xian Xu. A sufficient condition for a family of graphs being determined by their generalized spectra. European Journal of Combinatorics, 27(6):826–840, 2006.DOI
  18. [18]Richard P. Stanley. Smith normal form in combinatorics. Journal of Combinatorial Theory, Series A, 144:476–495, 2016.arxiv.org/abs/1602.00166
  19. [19]Aida Abiad, Carlos A. Alfaro, Kristin Heysse, and Marcos C. Vargas. Codeterminantal graphs. Linear Algebra and its Applications, 650:1–25, 2022.DOI
  20. [20]Lihong Qiu, Wei Wang, Wei Wang, and Hao Zhang. Smith normal form and the generalized spectral characterization of graphs. Discrete Mathematics, 346(1):113177, 2023.arxiv.org/abs/2108.00592
  21. [21]Gottfried Tinhofer. Graph isomorphism and theorems of Birkhoff type. Computing, 36(4):285–300, 1986.DOI
  22. [22]Motakuri V. Ramana, Edward R. Scheinerman, and Daniel Ullman. Fractional isomorphism of graphs. Discrete Mathematics, 132(1-3):247–265, 1994.DOI
  23. [23]Vikraman Arvind, Johannes Köbler, Gaurav Rattan, and Oleg Verbitsky. Graph isomorphism, color refinement, and compactness. Computational Complexity, 26(3):627–685, 2017.
  24. [24]H. A. Almohamad and S. O. Duffuaa. A linear programming approach for the weighted graph matching problem. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15(5):522–525, 1993.
  25. [25]Derek Justice and Alfred Hero. A binary linear programming formulation of the graph edit distance. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(8):1200–1214, 2006.pubmed.ncbi.nlm.nih.gov/16886857
  26. [26]Roger A. Horn and Charles R. Johnson. Topics in Matrix Analysis. Cambridge University Press, 1991.DOI
  27. [27]Laura Bahiense, Gordana Manić, Breno Piva, and Cid C. de Souza. The maximum common edge subgraph problem: A polyhedral investigation. Discrete Applied Mathematics, 160(18):2523–2541, 2012.
  28. [28]Julien Lerouge, Zeina Abu-Aisheh, Romain Raveaux, Pierre Héroüx, and Sébastien Adam. New binary linear programming formulation to compute the graph edit distance. Pattern Recognition, 72:254–265, 2017.DOI
  29. [29]Chris D. Godsil and Brendan D. McKay. Constructing cospectral graphs. Aequationes Mathematicae, 25(1):257–268, 1982.DOI
  30. [30]Edwin R. van Dam and Willem H. Haemers. Which graphs are determined by their spectrum? Linear Algebra and its Applications, 373:241–272, 2003.
  31. [31]Mathieu Dutour Sikirić, Achill Schürmann, and Frank Vallentin. Complexity and algorithms for computing Voronoi cells of lattices. Mathematics of Computation, 78(267):1713–1731, 2009.
  32. [32]Ishay Haviv and Oded Regev. On the lattice isomorphism problem. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 391–404. SIAM, 2014.arxiv.org/abs/1311.0366
  33. [33]Léo Ducas and Wessel van Woerden. On the lattice isomorphism problem, quadratic forms, remarkable lattices, and cryptography. In Advances in Cryptology – EUROCRYPT 2022, volume 13277 of Lecture Notes in Computer Science, pages 643–673. Springer, 2022.DOI
  34. [34]Christoph Berkholz and Martin Grohe. Limitations of algebraic approaches to graph isomorphism testing. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), volume 9134 of Lecture Notes in Computer Science, pages 155–166. Springer, 2015.arxiv.org/abs/1502.05912
  35. [35]Christoph Berkholz and Martin Grohe. Linear Diophantine equations, group CSPs, and graph isomorphism. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 327–339. SIAM, 2017.
  36. [36]Martin Grohe, Gaurav Rattan, and Tim Seppelt. Homomorphism tensors and linear equations. In Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 70:1–70:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022.
  37. [37]Garrett Birkhoff. Three observations on linear algebra. Universidad Nacional de Tucumán Revista, Serie A, 5:147–151, 1946.
  38. [38]Henry J. Stephen Smith. On systems of linear indeterminate equations and congruences. Philosophical Transactions of the Royal Society of London, 151:293–326, 1861.
  39. [39]Morris Newman. Integral Matrices. Academic Press, 1972.
  40. [40]Ravindran Kannan and Achim Bachem. Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM Journal on Computing, 8(4):499–507, 1979.DOI
  41. [41]Arne Storjohann. Near optimal algorithms for computing Smith normal forms of integer matrices. In Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation (ISSAC), pages 267–274. ACM, 1996.DOI
  42. [42]Arjen K. Lenstra, Hendrik W. Lenstra, and László Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534, 1982.
  43. [43]Joseph J. Rushanan. Eigenvalues and the Smith normal form. Linear Algebra and its Applications, 216:177–184, 1995.DOI
  44. [44]Charles R. Johnson and Morris Newman. A note on cospectral graphs. Journal of Combinatorial Theory, Series B, 28(1):96–103, 1980.DOI
  45. [45]Aida Abiad and Willem H. Haemers. Cospectral graphs and regular orthogonal matrices of level 2. The Electronic Journal of Combinatorics, 19(3):P13, 2012.
  46. [46]Wei Wang, Lihong Qiu, and Yulin Hu. Cospectral graphs, GM-switching and regular rational orthogonal matrices of level p. Linear Algebra and its Applications, 563:154–177, 2019.DOI
  47. [47]Robert C. Thompson. Interlacing inequalities for invariant factors. Linear Algebra and its Applications, 24:1–31, 1979.DOI
  48. [48]Casimir Kuratowski. Sur le problème des courbes gauches en topologie. Fundamenta Mathematicae, 15:271–283, 1930.DOI
  49. [49]H. C. von Warnsdorff. Des Rösselsprunges einfachste und allgemeinste Lösung. Th. Chr. Fr. Enslin, Schmalkalden, 1823.
  50. [50]Ira Pohl. A method for finding Hamilton paths and Knight’s tours. Communications of the ACM, 10(7):446–449, 1967.DOI
  51. [51]Allen J. Schwenk. Which rectangular chessboards have a Knight’s tour? Mathematics Magazine, 64(5):325–332, 1991.DOI
  52. [52]Ian Parberry. An efficient algorithm for the Knight’s tour problem. Discrete Applied Mathematics, 73(3):251–260, 1997.DOI
  53. [53]Laurent Perron and Vincent Furnon. OR-Tools. Google, https://developers.google.com/optimization/, 2024.
  54. [54]Christine Solnon. LIRIS / CNRS subgraph isomorphism benchmark suite (LIV and largerandom datasets). LIRIS Laboratory, CNRS / INSA Lyon, 2010.
  55. [55]Peter van Emde Boas. Another NP-complete partition problem and the complexity of computing short vectors in a lattice. Technical Report 81-04, Department of Mathematics, University of Amsterdam, 1981.
  56. [56]Miklós Ajtai. The shortest vector problem in L₂ is NP-hard for randomized reductions. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing (STOC), pages 10–19. ACM, 1998.

Paper details

vlnc:W_wmmjga2p
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 6

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents