Zhixian Lei

(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs

We consider the graph matching/similarity problem of determining how similar two given graphs $G_0,G_1$ are and recovering the permutation $\pi$ on the vertices of $G_1$ that minimizes the symmetric difference between the edges of $G_0$ and $\pi(G_1)$. Graph matching/similarity has applications for…