I was first interested in the “Paths” invariant, which is incredibly powerful test for discerning between potentially isomorphic graphs in cubic (and fully paralellizable) time, and was originally theorized to be a solution to GI. The primary findings of my thesis were that:
- [Computational Wrangling] Unlike was theorized, copaths graphs do exist, and finding them is easily done brute force calculations on today’s standard GPUs.
- [Theoretical Proof] Paths uniquely determines the chromatic polynomial of a graph.
- [Analytical Algorithms] Measuring discriminatory power to value ratio of invariants within graph isomorphism is possible and can help us devise better algorithms for practical isomorphism detection, and the paths invariant is well weighted in an analysis of discriminatory power.
- [Theoretical Proof] Paths as an invariant does not need to be calculated past N vertices.