Home

News

Overview

The Independent Set Reconfiguration (ISR) Problem

Definition

Example of input

It is illustrated as follows.


start state

target state

Example of output

It is illustrated as follows:

\(I_0 = I_s\) \(I_1\) \(I_2\) \(I_3 = I_t\)

File Format

Input file format

p 7 7
e 1 2
e 1 3
e 2 7
e 3 4
e 3 5
e 4 6
e 5 6
s 3 6 7
t 4 5 7

Output file format

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

Solver track

Note!

Clearly wrong outputs immediately result in disqualification.
  • Wrong reconfiguration sequence
  • Output "no" to an instance where a correct reconfiguration sequence exists

Graph track

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
      (Shortest Reconfiguration Sequence)

Schedule

Date Event
Nov. 24, 2021 Challenge is open (and you can join at any point)
1st benchmark is released
Dec. 31, 2021 2nd benchmark will be released
Submission details will be made public
Jan. 31, 2022 3rd benchmark will be released
Mar. 31, 2022, 23:59 (AoE, UTC-12) Challenge ends (submission deadline)
June. 8, 2022 Results open (Solver Track)
June. 13, 2022 Results open (Graph Track)

Registration

Submissions

Submissions are completed via github repositories.

For solver track

In the solver track, we ask you to submit the followings.

All you need to do to complete your submission is the following.

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.

Benchmark

Solution Validator

Award

Results

Organizers

Support

KAKENHI Grant-in-Aid for Transformative Research Areas (B)
"Fusion of Computer Science, Engineering and Mathematics Approaches for Expanding Combinatorial Reconfiguration"

Contact

FAQ