Problem

In what follows assume we are given two graphs. The first graph $G=(V,E)$ consists of a set of vertices $V$ and edges $E$ to which weights shall be assigned. The second graph $G_{emb}=(V_{emb},E_{emb})$ also consists of a set of vertices $V_{emb}$ and edges $E_{emb}$ and shall be a square King's Graph, with vertex labels as illustrated in the figure below. Under the constraints that we explain below, assign each vertex in $V$ to exactly one vertex in $V_{emb}$ such that the following score becomes as high as possible.

Score

For a given output of a source code in which each vertex in the graph $G$ is assigned to exactly one vertex in the graph $G_{emb}$, the score of the output is calculated as follows:

• The score is obtained by adding the weight of each edge of the graph $G$ connecting the vertices $u, v$, if the corresponding vertices in the graph $G_{emb}$ are connected by an edge.
• To evaluate your total score, we will run your algorithm on a total of $30$ input graphs $G$ (including 18 random graphs and 12 complete graphs) and add up the corresponding score.*