Graph Golf

The Order/degree Problem Competition

Rules 2017

Update 2017-03-06

Categories

The 2017 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 must be found. For the 2017 competition, the order/degree pairs (n, d) = (32, 5), (256, 18), (576, 30), (1344, 30), (4896, 24), (9344, 10), (88128, 12), (98304, 10), (100000, 32), (100000, 64) are featured.
Grid Graph Category
Do the same as above, but on a √n × √n square 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 2017 competition, the order/degree/length pairs (n, d, r) = (16, 3, 2), (256, 3, 3), (256, 3, 4), (256, 3, 15), (256, 6, 3), (256, 6, 4), (256, 6, 15), (256, 15, 3), (256, 15, 4), (256, 15, 15), (10000, 3, 6), (10000, 3, 18), (10000, 3, 33), (10000, 9, 6), (10000, 9, 18), (10000, 9, 33), (10000, 28, 6), (10000, 28, 18), (10000, 28, 33) 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 = 100000k + 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 l calculated as in [Cerf 1974].

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.

Schedule and tie-breaking rule

The competition goes through two phases: the closed submission period (before 2017-06-25) and the open submission period (after 2017-06-26). At the beginning, solutions accepted by 2017-06-25 23:59 UTC are reviewed and publicated on 2017-06-26. 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

© 2015-2021 National Institute of Informatics