The FHCP Challenge Set is a collection of 1001 instances of the Hamiltonian Cycle Problem, ranging in size from 66 vertices up to 9528 vertices, with an average size of just over 3000 vertices. The problems are in the standard HCP format (see below). All of the instances are designed to be difficult to solve using standard HCP heuristics. Every one of the 1001 graphs is known to be Hamiltonian.

 

Download the FHCP Challenge Set

 

Short URL: http://fhcp.edu.au/fhcpcs

 

COMPETITION OPENS: 30TH SEPTEMBER, 2015
COMPETITION DEADLINE : 30TH SEPTEMBER, 2016

 

The FHCP team is offering a $1001 (US) prize for the first researcher, or team of researchers, who can provide a solution for every graph in the set. If no team is successful in solving all 1001 graphs by the competition deadline, then the team which solved the largest number of graphs will win the prize, so research teams are encouraged to submit partial sets of solutions early and often!

 

CHALLENGE STATUS: Unsolved!

 

COMPETITION RULES

 

1) Individuals or teams may make multiple submissions, but only those solutions in their latest submission will be counted, so later submissions should also includes solutions discovered earlier.

2) Solutions will only be accepted until 11:59PM (GMT +9:30) on the 30th September, 2016.

3) The individual or team that solves the most graphs will be successful. In the event of a tie, the individual or team whose entry was received the earliest will be successful.

4) Solutions must be in the proper format (see below). If you are concerned, you should contact Michael Haythorpe with an example of a tour file to confirm that you are using the correct format.

5) Solutions should zipped in any standard archiving format (zip, rar, 7z, tar, gzip) and emailed to Michael Haythorpe.

6) Any queries or requests for clarification should be sent to Michael Haythorpe .

 

The FHCP Challenge Set competition was announced in the 59th Annual Meeting of the Australian Mathematical Society, held at Flinders University in September, 2015. The winners will be announced during the upcoming 60th Annual Meeting of the Australian Mathematics Society in 2016.

 

FORMATS

 

All graphs in the FHCP Challenge Set are in HCP format. A simple example of such a file is given below. The HCP file consists of a short header, an edge list, and a short footer.

 

Note that anything can be listed for NAME and COMMENT, while DIMENSION corresponds to the number of vertices. The other header and footer options should be unchanged.

 

NAME : Envelope graph
COMMENT : Example 6-vertex graph with HCs 1-2-3-6-5-4-1, 1-2-6-3-4-5-1 and 1-4-5-6-3-2-1
TYPE : HCP
DIMENSION : 6
EDGE_DATA_FORMAT : EDGE_LIST
EDGE_DATA_SECTION
1 2
1 4
1 5
2 3
2 6
3 4
3 6
4 5
5 6
-1
EOF

 

 

A tour file has a similar format, except instead of an edge list, it contains a list of vertices in the order visited in the Hamiltonian cycle, and the EDGE_DATA_FORMAT item is not required in the header.

 

NAME : Envelope tour file
COMMENT : Tour found
TYPE : TOUR
DIMENSION : 6
TOUR_SECTION
1
2
3
6
5
4
-1
EOF

 

CITING THE FHCP CHALLENGE SET

 

If you would like to cite the FHCP Challenge Set, you should cite it as:

 

M. Haythorpe. "FHCP Challenge Set." http://fhcp.edu.au/fhcpcs, 2015.