Graph Isomorphism (4 pts)
If you do project option 2, you have to do this problem. If you do project option 1, you have the choice to opt out and scale the final to 44%.
In this problem, we are going to solve the famous graph isomorphism problem (or do we?)!
Graph Isomorphism Problem (GI) is the following:
Given two undirected graphs G = (V, E) and G' = (V, E'), find a permutation f over V such that
for every e=(u, v) in E, (f(u), f(v)) in E'
People do not know whether there exists an efficient algorithm for GI, but it is generally believed that GI is not NP-Hard (but could still be hard for any polynomial time algorithms).
Input File
In this problem, you are given two graphs in the following file [graphs] (please do not try to open it by Windows text editor, use more professional tools like vim/Emacs/sublime/any other IDEs):
The first line consists of n and m, the number of vertices in G (or G') and the number of edges in G (or G')
The next m lines, each line consists of two numbers u, v --- one edge (u, v) in E
The next m lines, each line consists of two numbers u, v --- one edge (u, v) in E'
There is no duplicated edge or self loop in each graph.
Output File
Your goal is to output the permutation f in a file called ans [example].
In the ans file, you should have n lines:
the i-th line will contain a single number f(i)
Score
Your score is determined by how many edges your permutation f can match:
Let x = [the number of edges (u, v) in E such that (f(u), f(v)) is in E'] / m.
It indicates the fraction of edges you can match.
Your score for this problem is 5.333 * x^3 - 4 * x^2 + 2.667 * x.
You can use the checker to see your points.
Remark
You can use any programming language or any tool or AI agent, as long as you provide the final ans file. You will need to briefly explain how you get the answer, in the final homework.
Hint: since there is no known efficient algorithm for GI, you should not expect to design an algorithm that works for any graph. Your algorithm should be data dependent.