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. 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 vertices labeled from left to right and top to bottom, as illustrated in the figure below. The task is to find a map s which assigns each vertex i\in V to a subset of vertices s(i) ⊂ V_{emb} such that:

• For any vertex i \in V the subgraph induced by s(i) in G_{emb} is connected;
• The subsets s(i), s(j) ⊂ V_{emb} are mutually exclusive, i.e., for any i,j \in V with i\neq j we have s(i)∩ s(j)=Ø;
• For any vertex i \in V the subset s(i) must not be empty.

Score

For each run of your algorithm on a single input graph, the score obtained by the resulting map s is evaluated as follows:

• An initial score of 5000 points is assigned.
• We add 100 points to the initial score for each edge (i,j) \in E, if the corresponding vertex sets s(i), s(j) ⊂ V_{emb} are connected by at least one edge of the King's graph G_{emb}.
• We add a bonus of 100000 points, if the algorithm finds a map s such that for every edge (i,j)\in E, the corresponding vertex sets s(i), s(j) ⊂ V_{emb} are connected by at least one edge of the King's graph G_{emb}. Note that finding a map s which obtains the bonus score may not be possible on every input graph.
• Large clusters are penalized by subtracting ∑ _{u \in V} (|s(u)|-1) points from the score.
• The score becomes 0 in any of the following cases:
1. If the subgraph induced by any of the vertex sets s(i) in G_{emb} is disconnected. See Example 1 in the figure below.
2. If the vertex sets of s(i), s(j) are not mutually exclusive, i.e., if any of the vertex sets with (i \neq j) overlap on some element. See Example 2 in the figure below.
3. If the subset s(i) is empty, i.e., |s(i)| = 0.
4. Furthermore, any run of your algorithm which exceeds either the time or the memory limit will not contribute to your final score. The same is true for any output, which violates the output format specified below.

• For the period of the contest we will evaluate your score, by running your algorithm on 30 input graphs G and adding up the corresponding score. This will allow for a preliminary estimate of your rank.
• After the contest has finished your final score and rankings will be determined by running your final submission on 150 previously undisclosed input graphs.

Input Example 1

7 14
1 2
1 3
1 6
1 7
2 4
2 5
2 6
2 7
3 5
3 7
4 5
4 6
4 7
5 7
25 72
1 2
1 6
1 7
2 6
2 3
2 7
2 8
3 7
3 4
3 8
3 9
4 8
4 5
4 9
4 10
5 9
6 7
6 11
6 12
7 11
7 8
7 12
7 13
8 12
8 9
8 13
8 14
9 13
9 10
9 14
9 15
10 14
11 12
11 16
11 17
12 16
12 13
12 17
12 18
13 17
13 14
13 18
13 19
14 18
14 15
14 19
14 20
15 19
16 17
16 21
16 22
17 21
17 18
17 22
17 23
18 22
18 19
18 23
18 24
19 23
19 20
19 24
19 25
20 24
5 10
10 15
15 20
20 25
21 22
22 23
23 24
24 25

Output Example 1

3 14 15 20
1 19
1 9
1 23
1 18
1 25
1 13

The input example 1 from above is visualized in the figure below. The left side shows the input graph with 7 vertices, labeled by indices V1 to V7. The right side shows a King graph of size 5\times5. The map s as specified by the output of example 1 is visualized by colored boxes. For example, the vertex V1 of the input graph is mapped to a set of three vertices on the kings graph.

We now discuss the score assigned to the map s as specified by output example 1:

• The initial score is 5000 points.
• We add 11 \times 100 = 1100 points to the initial score, i.e., 100 points for every edge of the input graph, if the corresponding vertex sets are connected by at least one edge of the King's graph. To this end consider for example the edge between the vertex pair (V1, V2). Clearly, the corresponding vertex sets on the King's graph are connected. Therefore, we add 100 points for this edge. On the other hand, consider the vertex pair (V3, V5). The corresponding vertex sets on the King's graph are not connected. Therefore, this edge does not contribute to the score and we mark it by a red cross. Repeating this procedure for every edge of the input graph, we find that 11 edges of this example score, while 3 edges (as marked by a red cross) do not score.
• The bonus points of output example 1 are 0 because the vertex sets corresponding to some edges of the input graph (as marked by a red cross), are not connected by a direct edge of the King's graph.
• We subtract (3-1) + (1-1) + (1-1) + (1-1) + (1-1) + (1-1) + (1-1)= 2 points, where the first number in each bracket corresponds to the number of elements in each vertex set on the right. Altogether we lose 2 points because the vertex set s(V1) contains three elements.
• Altogether output example 1 scores because the vertex sets s(i) are mutually exclusive and each vertex set s(i) induces a connected subgraph of the King's graph.

Input Example 2

10 30
3 10
3 6
5 10
5 8
2 6
2 7
1 5
1 9
4 10
5 7
4 6
2 8
1 2
7 10
2 4
1 3
7 8
1 8
6 9
2 9
1 4
2 10
2 3
6 10
8 10
6 8
5 6
3 8
7 9
4 9
16 42
1 2
1 5
1 6
2 5
2 3
2 6
2 7
3 6
3 4
3 7
3 8
4 7
5 6
5 9
5 10
6 9
6 7
6 10
6 11
7 10
7 8
7 11
7 12
8 11
9 10
9 13
9 14
10 13
10 11
10 14
10 15
11 14
11 12
11 15
11 16
12 15
4 8
8 12
12 16
13 14
14 15
15 16

Output Example 2

1 5
2 7 10
1 1
1 2
1 12
1 6
1 15
1 9
1 4
4 3 8 11 14

The input example 2 corresponds to the following schematic figure.

Sample Code and References

• Sample code including source code for generating random input graphs and evaluating the corresponding score of your algorithm can be downloaded through the following link.
• For a previous study of the graph embedding problem, see:

J. Cai, et al., "A practical heuristic for finding graph minors", arXiv:1406.2741 [quant-ph]