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.