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

May 13, 2019, midnight UTC

July 22, 2019, midnight UTC

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

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.

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.

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].

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.

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.

**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.*

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.

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`= 1000000`k`+`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`= (`l`−`L`) ÷`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.

For a order `n` and a degree `d`, the lower bound `K _{n,d}` on the diameter

Similarly, the lower bound `L _{n,d}` on the ASPL

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.

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.

- 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

- 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.

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:

- Michihiro Koibuchi, National Institute of Informatics
- Ikki Fujiwara, National Institute of Informatics
- Shoichi Hirasawa, National Institute of Informatics
- Satoshi Fujita, Hiroshima University
- Koji Nakano, Hiroshima University
- Takeaki Uno, National Institute of Informatics
- Takeru Inoue, NTT Network Innovation Laboratories
- Ken-ichi Kawarabayashi, National Institute of Informatics

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

- graphgolf@nii.ac.jp

**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

**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

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

You must be logged in to participate in competitions.

Sign In