![Algorithmic Spectral Graph Theory_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Algorithmic%20Spectral%20Graph%20Theory_hi-res.jpg?h=bc58dfd7&itok=8NAdfoPF)
Abstract
Graphs are a ubiquitous mathematical abstraction employed in numerous problems in science and engineering. Of particular importance is the need to find best structure-preserving matching of graphs. Sincegraph matching is a computationally intractable problem, numerous heuristics exist to approximate its solution. An important class of graph matching heuristics is relaxation techniques based on replacing the original problem by a continuous convex program. Conditions for applicability or inapplicability of such convex relaxations are poorly understood. In this talk, I will show easy to check spectral properties characterizing a wide family of graphs for which equivalence of convex relaxation to the exact graph matching is guaranteed to hold.