Home
News
 Challenge is open (Nov. 24 2021).
Overview
 Combinatorial Reconfiguration is a novel algorithmic concept that provides mathematical models and analysis for "transformations over state spaces." Its appearance ranges from theory to applications. However, its technical achievements are hard to access. Thus, it is required to found a common infrastructure for utilizing and applying the algorithmic technology of combinatorial reconfiguration. See this website for more backgrounds.
 The 1st Combinatorial Reconfiguration Challenge (CoRe Challenge 2022) is a competition aiming for practically exploring the combinatorial reconfiguration.
 This 1st challenge targets the Independent Set Reconfiguration (ISR) problem.
 The ISR problem is one of the most wellstudied reconfiguration problems. Theoretically, the problem is PSPACEcomplete, which implies that there exist instances such that even a shortest reconfiguration sequence requires a super polynomial steps. Theoretical results and their references can be found in a survey by N. Nishimura.
The Independent Set Reconfiguration (ISR) Problem
Definition
 Input
 an undirected graph \(G=(V, E)\).
 two independent sets of \(G\): start state \(I_s\) and target state \(I_t\) where \(I_s = I_t\) holds.
 Output
 existence (yes or no) of a reconfiguration sequence from \(I_s\) to \(I_t\) under the reconfiguration rule (token jump).
 in case of yes, one reconfiguration sequence.
 Reconfiguration sequence under the token jump rule
 An independent set of \(G\) is a set of vertices in \(G\) such that no two vertices are adjacent.
 Suppose that a token is placed on each vertex in an independent set of \(G\).
 A reconfiguration sequence from \(I_s\) to \(I_t\) under the token jump rule is a sequence of independent sets of \(G\) which transforms \(I_s\) into \(I_t\) so that each independent set in the sequence results from the previous one by moving exactly one token to another vertex.
 The length of a reconfiguration sequence is the number of independent sets (including \(I_s\) and \(I_t\)) minus one, that is, the number of token moves.
Example of input
 undirected graph \(G\)
 \(V=\{1,2,3,4,5,6,7\}\)
 \(E=\{\{1,2\},\{1,3\},\{2,7\},\{3,4\},\{3,5\},\{4,6\},\{5,6\}\}\)
 start state \(I_s = \{3,6,7\}\)
 target state \(I_t = \{4,5,7\}\)
It is illustrated as follows.
start state 
target state 
Example of output
 existence of a reconfiguration sequence
 yes
 a reconfiguration sequence
 \((\{3,6,7\},\{1,6,7\},\{1,5,7\},\{4,5,7\})\)
 the length of this reconfiguration sequence
 3 (the number of independent set minus one)
It is illustrated as follows:
\(I_0 = I_s\)  \(I_1\)  \(I_2\)  \(I_3 = I_t\) 
File Format
Input file format

Each instance is given by two files
*.col
and*.dat
. col file describes an input graph structure in DIMACS format.
p
line describes the number of nodes and edgese
lines describe two endpoints of edges
 dat file describes start/target states.
s
line describes the start statet
line describes the target state
 col file describes an input graph structure in DIMACS format.

The following is the col file that describes the above example.
p 7 7
e 1 2
e 1 3
e 2 7
e 3 4
e 3 5
e 4 6
e 5 6
 The following is the dat file that describes the above example.
s 3 6 7
t 4 5 7
Output file format

Output is given by one file
*.out
.s
line denotes the start state.t
line denotes the target state.a
lines denote your answer. YES/NO, and
 reconfiguration sequence that includes start and target states.
c
lines denote information if any.

The following is an output file describes the above example.
c model ISR_TJ
s 3 6 7
t 4 5 7
a YES
a 3 6 7
a 1 6 7
a 1 5 7
a 4 5 7
Rules and Tracks
 Contestants (individuals or teams) can make submissions.
 Contestants can make submissions more than one track/metrics simultaneously.
 (solver#existent)
 (solver#shortest)
 (solver#longest)
 (graph#10)
 (graph#50)
 (graph#100)

Contestants will be evaluated by each track/metrics. In case of tie, the contestant whose submissions were received earlier will be successful.

Submissions will only be accepted until the deadline specified in the schedule.
 Submissions should be in the proper format and submitted in the proper way (see below).
 If you have any questions or concerns, please send them to Contact.
Solver track
 Contestants do the following:
 develop programs that output "yes/no" and "reconfiguration sequence (if yes)" for the ISR problem
 run programs on your own machine
 submit your results in the form of output files.
 Evaluation metrics are as follows:
 (solver#existent) the number of instances that contestants outputted "yes/no" and "reconfiguration sequence (if yes)"
 (solver#shortest) the number of instances that contestants outputted reconfiguration sequences having the shortest length among all contestants
 (solver#longest) the number of instances that contestants outputted reconfiguration sequences having the longest length among all contestants. Note that a sequence cannot contain any loop, i.e., two identical independent sets.
Note!
Clearly wrong outputs immediately result in disqualification. Wrong reconfiguration sequence
 Output "no" to an instance where a correct reconfiguration sequence exists
 See our ISR App page, which provides a prototype solver for (solver#existent) and (solver#shortest) metrics.
Graph track
 Contestants do the following:
 construct an input of the ISR problem that has a long shortest reconfiguration sequence
 graph
 start state
 target state
 submit your input in the form of input files together with output file which gives a shortest reconfiguration sequence for your input.
 construct an input of the ISR problem that has a long shortest reconfiguration sequence
 Evaluation:
 Each submission (ISR instance) is evaluated by its shortest reconfiguration sequence length.
 The shortest reconfiguration sequence is also practically checked by organizer.
 Graph size limitation is as follows:
 (graph#10) the number of vertices in a graph is at most 10
 (graph#50) the number of vertices in a graph is at most 50
 (graph#100) the number of vertices in a graph is at most 100
Example of Graph Track
 We are interested in ISR instances which are compact but have a long shortest reconfiguration sequence.
 For instance, the following ISR instance has 14 verticies and independent sets sized 6. The length of its shortest reconfiguration is indeed 12.
 Can you construct an ISR instance of 14 vertices whose shortest reconfiguration length is more than 12?

(Instance)
start state 
target state 
Schedule
Date  Event 

Nov. 24, 2021  Challenge is open (and you can join at any point) 
1st benchmark is released  
Dec. ~~2731~~ 31, 2021  2nd benchmark will be released 
Submission details will be made public  
Jan. ~~2428~~ 31, 2022  3rd benchmark will be released 
Mar. 31, 2022, 23:59 (AoE, UTC12)  Challenge ends (submission deadline) 
May. xx, 2022  Results open (sometime in May) 
Registration
 Join https://groups.google.com/g/corechallenge.
 you can receive update information for this challenge via the group.
 you can ask public questions and read ones by others.
 in case team, the registration of one person is mandatory.
 If you cannot to access the group, see FAQ.
 Deadline of the registration is the same as submissions (see schedule). However, we recommend you to register as early as possible so that you do not miss update information about the challenge.
 Of course, you can join the group for "just looking". Participation to the group does not immediately mean registration to the competition.
Submissions
Submissions are completed via github repositories.
For solver track
In the solver track, we ask you to submit the followings.
 your
solution
generated in your own environment, and  your
solver
executable in a Docker container.
All you need to do to complete your submission is the following.
 (1) clone https://github.com/corechallenge/2022submission which will be made public according to schedule.
 (2) put your materials accordingly, which will be your submission.
 all necessary explanations are in README.
 benchmark instances are available in https://github.com/corechallenge/2022benchmark.
 (3) create your own github privaterepository and push your submission to your repository.
 (4) add
TakehideSoh
as a member of your repository so that organizer can clone your submission. In case your submission has some problems, organizers will communicate by using
issue
of your repository.
 In case your submission has some problems, organizers will communicate by using
 Note: After the deadline, all submissions will be collected and pushed to challenge's public repository.
For graph track
In the graph track, we ask you to submit your ISR instance
.
All you need to do to complete your submission is the following.
 (1) clone https://github.com/corechallenge/2022submission which will be made public according to schedule.
 (2) put your ISR instance accordingly, which will be your submission.
 all necessary explanations are in README in the repository.
 (3) create your own github privaterepository and push your submission to your repository.
 (4) add a github account named
TakehideSoh
as a member of your repository so that organizer can clone your submission. In case that your submission has some problems, organizer will communicate by using
issue
of your repository.  After your submission, multiple updates (commits) are allowed until the deadline (see schedule).
 In case that your submission has some problems, organizer will communicate by using
 Note: After the deadline, all submissions will be collected and pushed to challenge's public repository.
Benchmark
 You can clone 1st benchmark set from https://github.com/corechallenge/2022benchmark.
 The 2nd and 3rd benchmark sets will be pushed to the same repository (see schedule).
 Your results are evaluated by using all sets: 1st, 2nd and 3rd benchmark sets.
Solution Validator
 You can find our official validator in here.
 Please check your solver's output by using this one.
Award
 Certificates will be awarded to participants who perform well in each track/metric.
Organizers
 Takehiro Ito (Tohoku University, Japan)
 Yoshio Okamoto (The University of ElectroCommunications, Japan)
 Takehide Soh (Kobe University, Japan)
Support
KAKENHI GrantinAid for Transformative Research Areas (B)
"Fusion of Computer Science, Engineering and Mathematics Approaches for Expanding Combinatorial Reconfiguration"
Contact
 For public questions, please use https://groups.google.com/g/corechallenge.
 You can join the group for "just looking". Participation to the group does not immediately mean registration to the competition.
 If you cannot to access the group see FAQ.
 For private questions, please use
core.challenge [at] grp.tohoku.ac.jp
.
FAQ

Q1. Google group cannot be displayed from my acccount.
 A1. You might use your Google Workspace account and your organization (e.g. university, company) do not allow to use outside google group. Please use a google account (e.g. xxx@gmail.com) other than ones of Google workspace (e.g. xxx@your.org).

Q2. What is the maximum size of the benchmark graph in the solver track?
 A2. The maximum size will be at most 10 thousand"s".