Graph Golf

Organized by ikfj - Current server time: May 23, 2019, 7:23 p.m. UTC

Current

Closed submission phase
May 13, 2019, midnight UTC

Next

Open submission phase
July 22, 2019, midnight UTC

End

Competition Ends
Oct. 14, 2019, 11:59 p.m. UTC

Welcome!

Find a graph with the smallest diameter and average shortest path length given an order and a degree.

Graph Golf is an international competition of the order/degree problem since 2015. It is conducted with the goal of making a catalog of smallest-diameter graphs for every order/degree pair. Anyone in the world can take part in the competition by submitting a graph. Outstanding authors are awarded in CANDAR'19, an international conference held in Nagasaki, Japan, in November 2019.

Problem definition

The order/degree problem with parameters n and d: Find a graph with minimum diameter over all undirected graphs with the number of vertices = n and degree ≤ d. If two or more graphs take the minimum diameter, a graph with minimum average shortest path length (ASPL) over all the graphs with the minimum diameter must be found.

The order/degree problem on a grid graph with a limited edge length r: Do the same as above, but on a w × h grid in a two-dimensional Euclidean space, keeping the lengths of the edges ≤ r in Manhattan distance. Here a "grid" implies that (1) the vertices are located at integer coordinates but are not necessarily connected to its adjacent vertices; and (2) the edges must not run diagonally while being allowed to change its direction at the grid points.

Why order/degree problem?

Graph design has a rich variety of application fileds of computer systems. In particular, it is just meeting a network design of future supercomputers and future high-end datacenters in terms of hop counts [SOCC11] [ISCA12] [SC14], since their networks are topologically modeled as undirected regular graphs. Low latency is preconditioned on small hop counts, but existing network topologies have hop counts much larger than theoretical lower bounds. Therefore, computer network designers desire to find a graph that has a small number of hops between any pair of vertices. The same solution is beneficial for desining such a micro network, though the layout of a graph on two-dimensional surface (on a chip) must be considered [MICRO07] [DATE14] [MICRO14].

Why not degree/diameter problem?

The degree/diameter problem (DDP) has been studied for decades and consists in generating the largest possible graph given degree and diameter constraints, striving to approach theoretical upper bounds [DDP-wiki]. However, DDP solutions may not be directly usable for network topologies in supercomputer and high-end datacenter systems because they are for particular number of compute nodes, whereas the number of nodes in a real system is determined based on practical considerations, e.g., budget.

Let me challenge!

You're welcome! Please visit http://research.nii.ac.jp/graphgolf/ to take part in the competition.

NOTE: The competition takes place on its own website. Do not submit your solutions to the CodaLab system. Those submissions are not evaluated properly (having a dummy score) and not considered for the awards.

Evaluation Criteria

NOTE: The competition takes place on its own website. Please visit http://research.nii.ac.jp/graphgolf/ to submit your solutions. Do not submit your solutions to the CodaLab system.

Categories

The Graph Golf 2019 competition consists of two categories:

General Graph Category
Find a graph with minimum diameter over all undirected graphs with the number of vertices = n and degree ≤ d. If two or more graphs take the minimum diameter, a graph with minimum average shortest path length (ASPL) over all the graphs with the minimum diameter should be found. For the 2019 competition, the order/degree pairs (n, d) = (50, 4), (512, 4), (512, 6), (1024, 4), (1726, 30), (4855, 15), (9344, 6), (65536, 6), (100000, 8), (1000000, 16), (1000000, 32) are featured. Note that the graphs can be non-regular.
Grid Graph Category
Do the same as above, but on a w × h grid in a two-dimensional Euclidean space, keeping the lengths of the edges ≤ r in Manhattan distance. Here a "grid" implies that (1) the vertices are located at integer coordinates but are not necessarily connected to its adjacent vertices; and (2) the edges must not run diagonally while being allowed to change its direction at the grid points. For the 2019 competition, the order/degree/length pairs (w×h, d, r) = (5×5, 4, 2), (5×10, 4, 2), (10×10, 4, 2), (10×10, 6, 3), (10×10, 8, 4), (20×20, 4, 2), (20×20, 6, 3), (20×20, 8, 4), (100×100, 4, 2), (100×100, 6, 3), (100×100, 8, 4) are featured.

Awards

Each category has two awards:

Widest Improvement Award
The widest improvement award goes to the authors who find the largest number of best solutions. The best solution means a graph with the smallest diameter, and with the smallest average shortest path length (ASPL) among those with the same diameter, for each order/degree(/length) pair. Formally speaking, we calculate score = 1000000k + l, where k is the diameter and l is the ASPL, and pick the graph with the lowest score as the best solution.
Deepest Improvement Award
The deepest improvement award goes to the authors who achieve the smallest ASPL gap over all the order/degree(/length) pairs. The ASPL gap is calculated as gap = (lL) ÷ L, where l is the ASPL of the graph and L is the lower bound of ASPL calculated as shown below.

Only those graphs that complies with the featured order/degree(/length) pair will be nominated for the awards. However, we also accept non-featured graphs and make them exhibited on the ranking page. We encourage you to submit your results no matter if featured or not.

Lower bound of diameter & ASPL

For a order n and a degree d, the lower bound Kn,d on the diameter k is computed as

Similarly, the lower bound Ln,d on the ASPL l is computed as

Schedule and tie-breaking rule

The competition goes through two phases: the closed submission period (before 2019-07-21) and the open submission period (after 2019-07-22). At the beginning, solutions accepted by 2019-07-21 23:59 UTC are reviewed and publicated on 2019-07-22. Afterwards, solutions accepted within a week are reviewed and publicated every Monday. Note that a week begins at Monday 0:00 UTC and ends at Sunday 23:59 UTC.

The first-to-file rule applies to those graphs with the same diameter and ASPL. For each order/degree(/length) pair, if two or more graphs have the same diameter and the same ASPL, only those graphs publicated at the earliest time will be nominated for the awards. If there are two or more such graphs publicated at the same time, all of them will be nominated.

Publication

When publicated, the submitted graph file will be made available for downloads. The submitetd graphs will also be publicated later at Grpah Bank, which is an open database of interesting graphs developed by the Graph Golf team.

Important dates

  • 2019-05-13: Closed submission phase starts
  • 2019-07-22: Open submission phase starts
  • 2019-10-14: Submission phase ends (deadline 2019-10-14 23:59:59 UTC)
  • 2019-10-21: Awards notification
  • 2019-11-26 (tentative): Workshop in CANDAR'19

Terms and Conditions

Q&A

Who can take part in the competition?
Anyone in the world who can use the online submission system has the right to take part in the Graph Golf competition. There are no limitations on age, position, etc.
How can I make a program that creates graphs?
A good starting point is "create-random.py" available at the bottom of the problem page. Using this Python script you can create a random graph and calculate its diameter and average shortest path length. You may extend this script to make your own program.
Do I have to submit graphs for all the featured order/degree pairs?
No, your entry is welcome even with a single graph.
Can I submit a graph with an arbitrary order/degree pair?
Yes, any graphs are accepted for submission. They will be listed in the solutions page. Remember that only those graphs with the featured order/degree pairs will be considered for the awards.
Do I have to enter my real name?
No, you can use a nickname. But please keep your nickname unique and consistent; don't use such a nickname as "xxx", "anonymous" or "a student".
We are a group. Can we enter all of our names?
Yes. If your graph wins the competition, all of the authors will be awarded.
Do I have to attend the conference?
No.
May I make a publication later about the submitted graphs?
Yes. The organizers do not claim copyright of the submitted graphs.
Would the competition be held every year?
Yes, the competition will be held every year changing the featured order/degree pairs.

About Graph Golf

Graph Golf is an international competition of the degree-order problem since 2015. It aims at making a catalog of smallest-diameter graphs in collabolation between graph theorists and computer scientists. Graph Golf is organized by:

If you have any questions or ideas, feel free to contact us:

  • graphgolf@nii.ac.jp

Closed submission phase

Start: May 13, 2019, midnight

Description: NOTE: The competition takes place on its own website. Please visit http://research.nii.ac.jp/graphgolf/. Do not submit your solutions to the CodaLab system. Those submissions are not evaluated

Open submission phase

Start: July 22, 2019, midnight

Description: NOTE: The competition takes place on its own website. Please visit http://research.nii.ac.jp/graphgolf/. Do not submit your solutions to the CodaLab system. Those submissions are not evaluated

Competition Ends

Oct. 14, 2019, 11:59 p.m.

You must be logged in to participate in competitions.

Sign In