2025/11/18 by Hoàng, Phuong N., McGoff, Kevin, Nobel, Andrew B. +2 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Extreme point #Graph #Graph homomorphism #Graph isomorphism #Isomorphism (crystallography) #Linear programming #Regular polygon #Vehicle Routing Optimization Methods #Vertex (graph theory)
paper · open access · doi:10.48550/arxiv.2511.14862
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2025/11/18 · openalex created_date 2025/11/23 · openalex updated_date 2026/07/28
We introduce an optimal transport based approach for comparing undirected graphs with non-negative edge weights and general vertex labels, and we study connections between the resulting linear program and the graph isomorphism problem. Our approach is based on the notion of a joining of two graphs G and H, which is a product graph that preserves their marginal structure. Given G and H and a vertex-based cost function c, the optimal graph joining (OGJ) problem finds a joining of G and H minimizing degree weighted cost. The OGJ problem can be written as a linear program with a convex polyhedral solution set. We establish several basic properties of the OGJ problem, and present theoretical results connecting the OGJ problem to the graph isomorphism problem. In particular, we examine a variety of conditions on graph families that are sufficient to ensure that for every pair of graphs G and H in the family (i) G and H are isomorphic if and only if their optimal joining cost is zero, and (ii) if G and H are isomorphic, the the extreme points of the solution set of the OGJ problem are deterministic joinings corresponding to the isomorphisms from G to H.