Skip to content

Rules and What Contestants Will Do?

General

  • Contestants (individuals or teams) can make submissions.
  • Contestants can make submissions of more than one track/metric simultaneously.
    • (solver#existent)
    • (solver#shortest)
    • (solver#longest)
    • (graph#17)
    • (graph#31)
    • (graph#59)
  • Contestants can make multiple submissions (at most 3) for each track/metric.
  • Contestants will be evaluated by each track/metric. In case of a tie, the contestant whose submissions were received earlier will be successful.
  • In the solver track, contestants submit their solver in the proper format that will be instructed Submissions.
    • Each solver is evaluated by the organizer.
    • The following machine will be used:
      • CPU: Core i5 12400(2.5GHz)
      • Mem: 64GB
    • We are planning to use 30 minutes for each instance.
  • In the graph track, contestants submit their ISR instances in the proper format that will be instructed Submissions.
  • 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
    • wrap your solver by virtual machine which will be instructed in Submissions.
    • submit your VM-wrapped solver.
  • 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

Solution Validator

  • You can find our official validator here.
  • Please check your solver's output by using this one.

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 files which gives the 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 the organizer.
    • Graph size limitation is as follows:
      • (graph#17) the number of vertices in a graph is at most 17
      • (graph#31) the number of vertices in a graph is at most 31
      • (graph#59) the number of vertices in a graph is at most 59

Example of Graph Track

  • We are interested in ISR instances that are compact but have a long shortest reconfiguration sequence.
  • For instance, the following ISR instance has 14 vertices 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)