The graph matching problem is to find a correspondence between vertices of two given graphs such that the number of induced edge disagreements is minimized. This problem is NP-hard in general. While the PATH algorithm achieves the state-of-the-art matching accuracy for random graphs, it is not known whether there is any guarantee for its matching accuracy in general. This thesis tries to answer the question above. It first studies the PATH algorithm in detail. Realizing that a direct proof is rather complicated, we analyze the algorithm’s performance based on experiments. It turns out that the solutions of the PATH algorithm can be arbitrarily bad. On Cai-Fürer-Immerman graphs, its solutions give worst
possible matching accuracy most of the time as graph size increases, which implies that such guarantee does not exist.