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 on vertices and a target graph on vertices, how hard is it to find a copy of inside —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 () 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 as a global linear operator rather than a collection of decoupled Boolean clauses, we:
unify square graph isomorphism () and rectangular subgraph isomorphism (, both induced and non-induced) in a single -variable Kronecker operator framework (§ 2) that naturally exploits modern multi-core CP-SAT and ILP solvers (§ 7–§ 8);
construct an explicit unimodular cycle basis for the doubly-stochastic lattice that connects the commutator kernel directly to generalized cospectrality and affine lattice norm minimization (§ 3–§ 4.3); and
introduce a projection of the rectangular commutator onto the -dimensional zero-sum difference lattice 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 ()
Consider two graphs, and , with corresponding adjacency matrices and , respectively. In the special case where both graphs have the same number of vertices (), Graph isomorphism between and () holds if and only if there exists a square permutation matrix such that:
Because is orthogonal (), multiplying on the right by yields the classical linear commutator equation:
Though previous work has often framed (1) as a doubly-stochastic continuous relaxation [21, 22, 23] or via penalty linearizations for weighted graph matching and edit distance [24, 25], one can utilize the vectorization operator (vec) and the Kronecker product () [26] to arrive at an exact linear system. Recall that for matrices , , and of compatible dimensions:
Here, stacks the rows of matrix into a single column vector, and the Kronecker product forms a block matrix where each entry of multiplies the entire matrix . Applying (2) to (1) (, for symmetric undirected graphs where ) yields the homogeneous linear system:
where is an column vector representing the vectorized permutation matrix . 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 exist within the nullspace:
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 on vertices and on (with ), one is searching for an injective mapping embedding the smaller graph into the larger target . In the linear formulation, this mapping is represented by a rectangular binary matrix where . For to represent a valid one-to-one injection, each row must sum to 1 and each column to at most 1:
where denotes the all-ones vector. Whereas traditional integer programming approaches to subgraph matching and graph edit distance introduce edge-product variables or dummy-vertex padding [25, 27, 28], even though is now rectangular and no longer orthogonal (), the linear commutator from Equation (1) still directly captures both non-induced subgraph isomorphism (, where must contain all edges of but may include extra edges) and induced subgraph isomorphism (, where both edges and non-edges must be preserved, i.e., and for the complement graphs and , with the all-ones matrix):
Theorem 1 (Rectangular Commutator Inequalities for Subgraph Isomorphism). Let be a rectangular injection matrix (, ). Then:
defines a non-induced subgraph isomorphism () if and only if:
defines an induced subgraph isomorphism () if and only if both and its complement satisfy the commutator inequality:
Proof. Let pattern vertex map to target vertex . Expanding entry of the rectangular commutator gives:
Because each column of contains at most one non-zero entry, there are two cases:
Part 1 (Target vertex is unmatched, ): The second term vanishes and holds automatically (and identically ). Unmatched target vertices impose no constraints on boundary edges leaving the embedded subgraph.
Part 2 (Target vertex is matched to a unique pattern vertex , ): Here all other entries in column are zero, so the commutator entry simplifies to:
Enforcing forbids , which holds if and only if for all mapped pairs, establishing non-induced SGI (Equation (4a)). By the exact same argument on the complement graphs, enforcing holds if and only if (or equivalently ) for all . Combining both inequalities forces across all matched pairs, establishing induced SGI (Equation (4b)).
Note that for any binary row-stochastic matrix () and binary adjacency matrices , the upper bound (and similarly for ) holds automatically at every entry and serves to tighten continuous LP relaxations. Written out entry-by-entry, each row of enforces , 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 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 , implies and hence for any polynomial with non-negative coefficients. While all empirical benchmarks in Sections 6–7 use only the base 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 Kronecker operator form of subgraph isomorphism:
Spectral Properties
Eigenvalue Structure
Returning to the Kronecker operator in Equation (3), its eigenvalues and eigenvectors follow directly from the classical Sylvester–Kronecker spectrum of and [16, 26].
Theorem 2 (Spectrum of [26]). If and are the eigenvalues of symmetric adjacency matrices and with corresponding eigenvectors and , then has eigenvalues for all with corresponding eigenvectors .
Proof. Recall the mixed-product property of Kronecker products: . Let , where and are the -th and -th eigenvectors of and , respectively:
And, by symmetry:
Because is an eigenvector of both and , subtracting the two equations yields:
Thus for all 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 . Then:
That is, if the rank of the Kronecker commutator is consistent across , , and , then is cospectral to .
Proof. Let denote the union of distinct eigenvalues of the symmetric matrices and , with multiplicities in and in . Because and are orthogonally diagonalizable, equals the number of pairs for which by Theorem 2. Thus , and similarly and . Subtracting from yields the sum of squares:
Consequently, implies , which holds if and only if for every , i.e., .
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):
Which is to say, if , then a vector exists satisfying the above. Of course, one knows that 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 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
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 generated by integer combinations of basis vectors (). In matrix space (), requiring all row sums and all column sums of a matrix to equal a common scalar ( and ) imposes independent linear equations. Consequently, the subspace of generalized doubly-stochastic matrices has dimension [37]:
Rather than enforcing row and column sum equations externally, we can construct an explicit integral basis matrix directly from elementary permutation cycles anchored at vertex 0:
The Identity (1 column): .
Primary 2-Cycles ( columns): The vectorized star transpositions for .
Secondary 3-Cycles ( columns): The vectorized anchored 3-cycles for all ordered pairs .
Stacking these elementary cycle permutations forms an explicit unimodular basis matrix for the integer doubly-stochastic lattice:
Because every column of is a permutation matrix with row and column sum 1, substituting () into Equation (3) automatically enforces equal row and column sums and projects the Kronecker commutator directly onto the permutation lattice:
or, left-multiplying by to obtain a square symmetric operator on :
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 , 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 [34, 35], we can compute its Smith normal form (SNF) [18, 38, 39] in polynomial time [40, 41]:
where and are unimodular integer matrices () and is diagonal with elementary integer divisors satisfying .
For example, on the smallest cospectral non-isomorphic pair (, Figure 1)—the star and the 4-cycle plus isolated vertex , which share spectrum —the unprojected commutator nullspaces are of equal dimension ( in Theorem 3). Projecting onto the 17-dimensional doubly-stochastic basis , however, immediately separates both their Smith normal form diagonals and their nullspace dimensions (Theorem 5):

Figure 1. Isometric 2D lattice slices comparing the unprojected integer nullspace (top row) and the Theorem 4 doubly-stochastic lattice (bottom row) on the unit-sum slice against the permutation norm sphere (): (a) unprojected isomorphic slice intersecting at ; (b) unprojected cospectral slice with interior vectors () and empty annulus ; (c) doubly-stochastic isomorphic slice (), where the interior is empty, lie on , and non-permutations satisfy ; (d) doubly-stochastic cospectral slice (), where interior vectors are eliminated and all lattice points are pushed outside to , leaving the entire ball around empty.
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 denotes the columns of corresponding to zeros on the diagonal of , mapping back to the ambient space via yields the exact integral generator for the intersection of the commutator nullspace with the doubly-stochastic lattice:
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 of .
Note that 10 of the 11 raw basis vectors in resulting directly from the SNF are actual automorphism permutation matrices of , which affine-linearly generate all automorphisms. Moreover, running the Lenstra–Lenstra–Lovász (LLL) lattice reduction algorithm [42] cleanly isolates and the nine elementary leaf swaps. Though can obviously grow much faster than the lattice dimension 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 and . Moreover, though the lattice isomorphism problem (LIP) is known to be at least as hard as graph isomorphism (GI 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 walk matrix to study generalized cospectrality [17, 19, 20, 44, 45, 46]. However, walk-matrix methods require the graph to be controllable () and degenerate on regular graphs where collapses to rank 1. Projecting the Kronecker commutator directly onto the cycle basis bypasses walk vectors entirely—operating on arbitrary (including regular) graphs, capturing both and its complement in a single operator, and extending naturally to rectangular subgraph isomorphism (, § 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 satisfy Equation (10) (or Equation (11)) on the unit-sum affine slice , with ambient matrix . Then:
whereas every non-permutation solution with satisfies .
Proof. For any integer matrix with row and column sums , we have . Since holds for every integer with equality if and only if , and is even whenever , summing over all entries yields:
with equality (which with and means ), and whenever . Finally, for , left-projection by is lossless because is symmetric with zero diagonal, and the only symmetric matrix with zero diagonal in is ; hence .
Theorem 5 (Smith Normal Form Invariants and Generalized Cospectrality). Let . For graphs satisfying in Theorem 3 [17, 44]:
Proof. Let and denote the orthogonal projectors onto the -eigenspaces and , and set and . Any in satisfies (so ) together with and , which implies and for every . On the slice, maps into , contributing dimensions. Furthermore, taking the inner product with yields
Thus a solution exists (adding to as in and ) if and only if for all . Together with from , equality of the main projections across all eigenspaces is equivalent by the Johnson–Newman theorem [44] to and .
Theorem 6 (Rational Denominators and Invariant Factors). Let denote the commutator restricted to the -dimensional zero-sum difference lattice (generated by in § 4.4), with non-zero Smith normal form invariant factors [18, 43]. Any regular rational orthogonal matrix (, ) of level [17] decomposes around a reference permutation as , where () satisfies the inhomogeneous integer system . Whenever has full column rank (or on the normal component ), the level satisfies:
Consequently:
Trivial Torsion Certifies Isomorphism: If , then , forcing with .
Immunity to Fractional Switching: If , the pair cannot be related by any such rational switching operation of level . In particular, if is odd, no full-rank cospectral mate can be generated by standard Godsil–McKay switching () [29].
Proof. Because and , the difference has zero row and column sums, so for a unique coordinate vector whose least common denominator equals (since is unimodular on ). Substituting into yields , where . Writing the rectangular Smith normal form with unimodular and , the top rows give . Since every divides and is unimodular over , it follows that , and therefore .
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
When , moving from square permutations to rectangular injections introduces two obstacles that are absent when :
Asymmetric Column Sums Under Vertex Relabeling: When , every permutation matrix has column sums , which is invariant under any relabeling of ’s vertices. When , however, a rectangular injection matches columns of (column sum 1) and leaves columns unmatched (column sum 0). Including a reference injection such as in the lattice basis would uniquely identify the first vertices of , meaning that any relabeling of the vertices of would permute the 1s and 0s across columns and alter the resulting Smith normal form.
Boundary Edges Leaving the Subgraph: Even when is an induced subgraph of , edges in connecting the matched vertices to the unmatched vertices create non-zero entries in the unmatched columns of .
Both obstacles disappear if we consider differences between candidate injections rather than individual injection matrices.
If are any two rectangular injections mapping onto the same -vertex subset of , their difference matrix exhibits two exact cancellations:
(i) Row sums vanish: Because each row of and sums to 1 (every vertex of is mapped exactly once), every row of sums to , giving .
(ii) Column sums vanish universally: On the matched columns, both matrices have column sum 1, so . On the unmatched columns, neither matrix has any entries, so . Thus every column sum of is identically zero, giving .
This motivates restricting our algebraic analysis to the zero-sum difference lattice:
Working in neatly eliminates both obstacles:
Subset and Relabeling Independence: Because every column sum in is regardless of which columns are matched or unmatched, does not depend on which vertices of are chosen. Permuting the vertices of or () simply permutes the rows and columns of , mapping bijectively onto itself via a unimodular transformation in .
Boundary Edge Annihilation: Because the row and column sums of vanish identically, projecting the commutator operator onto cancels the contributions of boundary edges exiting the subgraph, isolating the internal commutator structure of the induced copy.
Geometrically, is the -dimensional lattice of integer swap moves (the tangent space of zero-sum perturbations to doubly-stochastic assignments), generated unimodularly by the elementary pairwise swap differences:
Writing for the matrix whose columns are , define the projected commutator matrices:
of dimensions and , separated by the dimension gap:
Theorem 7 (SNF Interlacing for Induced Subgraphs). Let ( vertices) and ( vertices) be graphs with projected commutator matrices and as in Equation (18). Let
denote the diagonal invariant factors of and ordered with non-zero divisors first () followed by zeros.
If , then for every , the Smith normal form invariants satisfy the divisibility sandwich:
and the nullspace dimensions satisfy the lower bound:
Proof. Suppose . By relabeling the vertices of via a permutation matrix (which acts on via a unimodular basis matrix and leaves invariant), we may place the induced copy of on the first vertices of :
where encodes the boundary edges between and . Partition the basis into the cycle matrices () supported on the first columns—which are precisely the basis matrices of padded with zero columns, —and the remaining cycle matrices . For any two padded matrices and in , the commutator evaluates to:
When we project against on the left, the zero columns of multiply the boundary block by zero, annihilating all boundary edges:
Thus the top-left principal submatrix of is identically . Because is obtained from by deleting rows and columns, the classical Smith normal form submatrix interlacing theorem [47] guarantees for all , and Cauchy rank interlacing yields Equation (21).
Theorem 8 (SNF Interlacing for Non-Induced Subgraphs). Let ( vertices) and ( vertices) be graphs where every vertex of has degree at least . If no two vertices of degree in share an edge, then satisfies Equations (20) and Equation (21) of Theorem 7.
Proof. Suppose . Each matched vertex in already uses at least edges to match the edges of . Any extra edge in between two matched vertices would increase both of their degrees in to at least . Since no two vertices of degree in share an edge, no such extra edge can exist, so 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 or , which is to say that rejecting and (along with candidate subdivisions on 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 (, , Figure 2a), formed by joining two polar hubs to an equatorial 5-cycle . 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):

Figure 2. Inversion certificate on the planar Pentagonal Bipyramid (): (a) the equatorial pentagon (, blue) passes Theorem 7 with zero violations; (b) the Kuratowski clique () has universal signature and is rejected via ; (c) the utility graph () has universal signature and is rejected via .
Case 1 (Kuratowski Clique , Refuted): Here , , , and . Because is a complete graph (so induced and non-induced containment coincide) and commutes with every permutation matrix, :
At , we have , whereas at we have . Because , , and , Theorem 7 immediately refutes (and the nullity bound (21) also fails: ). In fact, because universally, any -vertex graph containing must satisfy .
Case 2 (Utility graph , Refuted): Here , , , , and the shift is :
At , we have , whereas at we have . Because (and at , ), Theorem 7 immediately refutes (and the nullity bound (21) also fails: ).
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 (, , Figure 3a), formed by joining two degree-4 hubs via three paths of length 2 and one path of length 3. Because the only two vertices of degree are the non-adjacent hubs , Theorem 8 applies directly to every cycle , and testing the cycle ladder determines the largest cycle that can possibly exist inside a priori (Figure 3):

Figure 3. A priori maximum cycle bound via on a 2-connected host graph (deg , ): (a) with its longest cycle highlighted in green; (b) (, ) passes Theorem 7 with zero violations; (c) (, ) is rejected via and ; (d) (, ) is rejected via and , establishing as the maximum possible cycle length.
Case 1 (5-Cycle , Passes): Here , , , ,
and the shift is :
For , , and for , . The nullity bound (21) also holds (), matching the green 5-cycle (3–5–6–7–4–3) in Figure 3a. The possibility of a has not been rejected.
Case 2 (6-Cycle , Refuted): Here , , , , and the shift is :
At , we have , whereas at we have . At , we have , whereas at we have . Because , , and , Theorem 7 immediately refutes (and the nullity bound (21) also fails: ).
Case 3 (7-Cycle , Refuted): Here , , , and the shift is :
At , we have , whereas at we have . Because (and at , with nullity ), Theorem 7 immediately refutes (and restricting to the five zero-slack degree-2 vertices similarly rules out chorded ). Together, Cases 1–3 certify a priori that () is the largest possible cycle in .
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 (or punctured “Swiss-Cheese”) chessboard exactly once and, potentially by extension, return to its starting square.
In our algebraic framework, the host graph on an board has a natural Kronecker structure: every knight jump combines a stride-1 shift along one axis with a stride-2 shift along the perpendicular axis, so the full board adjacency matrix is the sum of two Kronecker outer products:
Finding a closed -step tour inside an -square active board () is the subgraph isomorphism problem for the cycle . This setting provides a visual, end-to-end demonstration of how our three tools interact:
SNF Subgraph Interlacing (, Theorem 7): Certifying the maximum possible closed sub-tour on small boards directly from the invariant factors of (§ 6.1).
Degree-2 Edge Pruning & Torsion Sieving (): 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.
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 (): Why the Chessboard Has a 10-Cycle But No Closed Tour
A classic puzzle asks why the chessboard ( squares, knight moves) admits an open Knight’s Tour (), yet admits no closed Knight’s Tour (), and what the longest closed tour on the board actually is. Because the board is bipartite (6 White and 6 Black squares), any closed cycle must have even length . Probing and via certifies a priori why no closed 12-cycle exists while permitting the 10-step closed tour shown in Figure 4a:

Figure 4. SNF cycle sieve on the classic chessboard (, ): (a) the closed 10-step sub-tour (, green, omitting middle-edge squares 5 and 8) passes Theorem 7 with zero violations; (b) the full 12-step cycle () is rejected on raw via and ; (c) pruning the two red dashed chords saturated by the eight degree-2 squares splits into two disjoint 6-cycles (orange and blue), whose 6-cycle torsion () fails and certifies as the longest closed tour.
Case 1 (Closed 10-Step Sub-Tour , Passes): Here , , , , and the shift is :
(length 81)
(length 99)
For , ; for , ; for , divides and (while for , ). 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 on Raw , Refuted): Here , , , and the shift is :
At , we have , and at , we have (41 total violations; nullity ).
Case 3 (Full 12-Step Tour on Degree-2 Pruned , Refuted): What if a 12-cycle used the two extra edges of () as chords? On the board, eight squares have degree 2, so any 12-cycle must use both incident edges of all eight squares. This saturates the four remaining degree-3 squares and forces the two cross-chords and to be unused (red dashed lines in Figure 4c). Deleting those two dead chords yields a 2-regular graph () on which any 12-cycle would have zero slack (). Yet still fails Theorem 7:
At , whereas ( and ), and the nullity drops from 21 to 18. Geometrically, pruning the two saturated chords splits the board into two disjoint 6-cycles (, orange and blue in Figure 4c), replacing 12-cycle torsion with 6-cycle torsion and proving that is the maximum closed Knight’s Tour on a 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 binary decision variables :
together with the complement constraint when solving for induced subgraphs. In all benchmarks below, our solver (Commutator SGI) passes this base 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 of § 4.1 or higher-order walk inequalities ().
The Swiss-Cheese Knight’s Tour Showdown (8 × 8, 10 × 10, and 12 × 12)
Scaling up to , , and chessboards with balanced White/Black punctures (), 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 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 Instance | W+P Heur (All Starts) | W+P Exact (Backtrack) | C++ Glasgow | C++ FASTiso | C-LAD (Solnon) | C-VF2 (Foggia) | Commutator SGI [Ours] |
| KT1. Closed Tour (10 Holes, SAT) | FAIL (0/54) | TIMEOUT (> 21600s) | TIMEOUT (> 21600s) | True (4.30s) | True (0.02s) | TIMEOUT (> 21600s) | True (0.48s) |
| KT2. Closed Tour (8 Holes, UNSAT) | FAIL (0/56) | TIMEOUT (> 21600s) | False (0.01s) | TIMEOUT (> 21600s) | False (0.00s) | TIMEOUT (> 21600s) | False (0.07s) |
| KT3. 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. Trap (10 Holes, ) | FAIL (0/54) | TIMEOUT (> 21600s) | False (0.00s) | TIMEOUT (> 21600s) | False (0.00s) | TIMEOUT (> 21600s) | False (0.06s) |
| KT5. 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. Trap (14 Holes, ) | FAIL (0/50) | False (0.00s) | False (0.01s) | TIMEOUT (> 21600s) | False (0.00s) | TIMEOUT (> 21600s) | False (0.08s) |
| KT7. Trap (20 Holes, ) | FAIL (0/80) | TIMEOUT (> 21600s) | False (0.01s) | TIMEOUT (> 21600s) | False (0.00s) | TIMEOUT (> 21600s) | False (0.27s) |
| KT8. Trap (16 Holes, ) | FAIL (0/84) | FAIL (0/84) | False (0.01s) | TIMEOUT (> 21600s) | False (0.00s) | TIMEOUT (> 21600s) | False (0.29s) |
| KT9. Trap (20 Holes, ) | FAIL (0/80) | TIMEOUT (> 21600s) | TIMEOUT (> 21600s) | TIMEOUT (> 21600s) | False (0.06s) | TIMEOUT (> 21600s) | False (0.69s) |
| KT10. Trap (20 Holes, ) | FAIL (0/80) | TIMEOUT (> 21600s) | TIMEOUT (> 21600s) | TIMEOUT (> 21600s) | False (0.00s) | TIMEOUT (> 21600s) | False (0.85s) |
| KT11. Trap (24 Holes, ) | FAIL (0/120) | TIMEOUT (> 21600s) | False (0.01s) | TIMEOUT (> 21600s) | False (0.00s) | TIMEOUT (> 21600s) | False (0.80s) |
| KT12. Trap (26 Holes, ) | FAIL (0/120) | TIMEOUT (> 21600s) | False (0.01s) | TIMEOUT (> 21600s) | False (0.00s) | TIMEOUT (> 21600s) | False (0.78s) |
| Summary: Solved / 12 (Timeouts) | 1/12 | 3/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).

Figure 5. Swiss-Cheese Hamiltonian Knight’s Tour Showdown (1,000 s timeout ceiling): (a) Per-instance log-scale runtime across 12 punctured , , and boards (solid bars = solved; hatched bars = timeout at 1,000 s); (b) Cumulative survival / cactus profile from s to 1,000 s across all 7 solvers.

Figure 6. Three-Panel Visual Gallery of Swiss-Cheese Knight’s Tour Graphs: (a) Closed Hamiltonian Tour on Seed 84 (, solved in 0.48s where Warnsdorff+Pohl fails 54/54 starts); (b) Closed Hamiltonian Tour on Seed 29 (12 Holes, , solved in 0.33s where Glasgow, FASTiso, VF2 & Warnsdorff Backtracking all either timeout or take > 10s); (c) Balanced Parity Trap on Seed 48 (, UNSAT refuted in 0.83s, highlighting the forced degree-2 corridors that prevent a global cycle).
Why Subgraph Backtracking Solvers Struggle on (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 , every pattern vertex has identical degree 2 and identical -step neighborhood profiles, so every target square with 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 s via root-level Hall filtering or times out completely at 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 or a direct local Hall marriage violation. Root-level degree and Hopcroft–Karp filtering detects the dead end in s without branching.
Hard Degree- Bottleneck Traps (KT7 Seed 48 and KT10 Seed 73): On KT7 (Figure 6c) and KT10, the board is connected, bipartite-balanced (), every single square has , and the White-to-Black biadjacency matrix has full rank (), 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 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 (), both boards contain a hub square adjacent to three degree-2 squares (). Because three forced degree-2 edges converging on a single vertex cannot be accommodated by a 2-regular cycle (, so ), both boards are certified UNSAT in 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 (), 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 & Instance | C++ 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 (, 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 (, 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 (, 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 (, 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 ( in , 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 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.

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
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]Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
- [2]Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II. Journal of Symbolic Computation, 60:94–112, 2014.
- [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]Martin Grohe and Pascal Schweitzer. The graph isomorphism problem. Communications of the ACM, 63(11):128–134, 2020.DOI
- [5]Julian R. Ullmann. An algorithm for subgraph isomorphism. Journal of the ACM, 23(1):31–42, 1976.DOI
- [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]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]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]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]Christine Solnon. AllDifferent-based filtering for subgraph isomorphism. Artificial Intelligence, 174(12-13):850–864, 2010.DOI
- [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]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]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]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]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]Chris Godsil and Gordon Royle. Algebraic Graph Theory, volume 207 of Graduate Texts in Mathematics. Springer, 2001.DOI
- [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]Richard P. Stanley. Smith normal form in combinatorics. Journal of Combinatorial Theory, Series A, 144:476–495, 2016.arxiv.org/abs/1602.00166
- [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]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]Gottfried Tinhofer. Graph isomorphism and theorems of Birkhoff type. Computing, 36(4):285–300, 1986.DOI
- [22]Motakuri V. Ramana, Edward R. Scheinerman, and Daniel Ullman. Fractional isomorphism of graphs. Discrete Mathematics, 132(1-3):247–265, 1994.DOI
- [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]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]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]Roger A. Horn and Charles R. Johnson. Topics in Matrix Analysis. Cambridge University Press, 1991.DOI
- [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]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]Chris D. Godsil and Brendan D. McKay. Constructing cospectral graphs. Aequationes Mathematicae, 25(1):257–268, 1982.DOI
- [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]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]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]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]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]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]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]Garrett Birkhoff. Three observations on linear algebra. Universidad Nacional de Tucumán Revista, Serie A, 5:147–151, 1946.
- [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]Morris Newman. Integral Matrices. Academic Press, 1972.
- [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]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]Arjen K. Lenstra, Hendrik W. Lenstra, and László Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534, 1982.
- [43]Joseph J. Rushanan. Eigenvalues and the Smith normal form. Linear Algebra and its Applications, 216:177–184, 1995.DOI
- [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]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]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]Robert C. Thompson. Interlacing inequalities for invariant factors. Linear Algebra and its Applications, 24:1–31, 1979.DOI
- [48]Casimir Kuratowski. Sur le problème des courbes gauches en topologie. Fundamenta Mathematicae, 15:271–283, 1930.DOI
- [49]H. C. von Warnsdorff. Des Rösselsprunges einfachste und allgemeinste Lösung. Th. Chr. Fr. Enslin, Schmalkalden, 1823.
- [50]Ira Pohl. A method for finding Hamilton paths and Knight’s tours. Communications of the ACM, 10(7):446–449, 1967.DOI
- [51]Allen J. Schwenk. Which rectangular chessboards have a Knight’s tour? Mathematics Magazine, 64(5):325–332, 1991.DOI
- [52]Ian Parberry. An efficient algorithm for the Knight’s tour problem. Discrete Applied Mathematics, 73(3):251–260, 1997.DOI
- [53]Laurent Perron and Vincent Furnon. OR-Tools. Google, https://developers.google.com/optimization/, 2024.
- [54]Christine Solnon. LIRIS / CNRS subgraph isomorphism benchmark suite (LIV and largerandom datasets). LIRIS Laboratory, CNRS / INSA Lyon, 2010.
- [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]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.
