Home

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 well-studied reconfiguration problems. Theoretically, the problem is PSPACE-complete, 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 edges
    • e lines describe two endpoints of edges
  • dat file describes start/target states.
    • s line describes the start state
    • t line describes the target state

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

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

Schedule

Registration

• Join https://groups.google.com/g/core-challenge.
  • 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/core-challenge/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/core-challenge/2022benchmark.
• (3) create your own github private-repository 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.
• 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/core-challenge/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 private-repository 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).
• 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/core-challenge/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.

Results

• Please see the result page.

Solvers Submitted

• Please see the solver showcase.

Organizers

• Takehiro Ito (Tohoku University, Japan)
• Yoshio Okamoto (The University of Electro-Communications, Japan)
• Takehide Soh (Kobe University, Japan)

Support

KAKENHI Grant-in-Aid 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/core-challenge.
  • 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".

• Q3. multiple submission is allowed?

  • A3. Yes. There may be a case that you have two-types of solvers, e.g.
    • one is good at SAT (sequence finder) and another one is good at UNSAT (prover)
    • one is good at shortest and another one is good at longest
  • In thise case, we recommend you to separate your submission by submitting two repositories.
  • Except that, there will be a case your solver entries into the both #exitent and #shortest and you use the same solver.
  • In this case, single submission is fine.

• Q4. docker container must be on Ubuntu 20.04?

  • A4. Yes and no. We are still recommending to use 20.04. But for some reason you need to use 18.04, it is okay. In this case, please let us know in your submission.

• Q5. What do I need to include in the solver description?

  • A5. In addition to your solver description, please include the followings:
    • a. which metric you entry in
    • b. solver type (portfolio or single-engine)
      • portfolio: your solver contains multiple solvers or algorithms
      • single-engine: your solver contains single solver or algorithm
    • c. computational environment: spec of your computer

• Q6. When I should submit? Earlier is better?

  • In case that two over-all results are tie, ealier solver submission will be successful.
    • But, the evaluation does not run for each instance.
    • the evaluation starts after the submission has completed (results, docker, solver, descrption).
  • And, the first priority is that the submission is perfect state.
  • In the case, the submission is perfect, it is better to submit it early (but at least after 3rd benchmark released).
  • So we recommend you to take enough time to polish up your submission.

• Q7. The solver in docker container should be the same one that obtained results submitted?

  • Yes. Please make your image so that we get the same result when we run it on the same computational environment described in the solver description.