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.
Related
- Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph
- Algebraic Structure and Orthogonality Properties of Rational Polynomial Phase Rings on Discrete Lattices
- On The Cyclicity of Algebraic Lattices
- Class numbers and finiteness of norm Euclidean quadratic lattices over algebraic number fields
- Scentree: a framework for generating scenario trees for multistage stochastic programming
BibTeX
@misc{gipson2026subgraph,
title = {{Subgraph Isomorphism, Integer Linear Programming, and Lattices: A Linear Algebraic Framework}},
author = {Bryant Gipson},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33235},
eprint = {2610.33235},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33235},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Subgraph Isomorphism, Integer Linear Programming, and Lattices: A Linear Algebraic Framework
AU - Bryant Gipson
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.33235
UR - https://arxiv.org/abs/2610.33235
AB - 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.
ER -