KR2026Proceedings of the 23rd International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 23rd International Conference on Principles of Knowledge Representation and Reasoning

Lisbon, Portugal. July 20-23, 2026.

Edited by
  1. Renata Wassermann
  2. Marie-Laure Mugnier
  3. Franz Baader

ISSN: 2334-1033
ISBN: 978-1-956792-18-8

Sponsored by
Published by

Copyright © 2026 International Joint Conferences on Artificial Intelligence Organization

SRIP: A SAT-based System for Independent Set Reconfiguration

  1. Takehide Soh(Nagoya University, Nagoya, Japan)
  2. Akifumi Kuwahara(Kobe University, Kobe, Japan)
  3. Mutsunori Banbara(Nagoya University, Nagoya, Japan)
  4. Naoyuki Tamura(Kobe University, Kobe, Japan)
  5. Yasuaki Kobayashi(Hokkaido University, Sapporo, Japan)
  6. Yuta Nozaki(Hokkaido University, Sapporo, Japan, SKCM2, Hiroshima University, Hiroshima, Japan)
  7. Takehiro Ito(Tohoku University, Sendai, Japan)
PDF
BibTeX
https://doi.org/10.24963/kr.2026/72

Keywords

  1. null-Independent Set Reconfiguration
  2. null-Token Jumping
  3. null-SAT
  4. null-Bounded Model Checking
  5. null-Clique Partitioning

Abstract

We present SRIP, a SAT-based system for solving the Independent Set

Reconfiguration Problem (ISRP) under the Token Jumping (TJ) rule.

SRIP formulates ISRP with SAT problems employing a clique-partition-based

constraint model and a set of pruning constraints that strengthen

propagation and reduce the search space for reconfiguration. The resulting

model is compiled into a sequence of SAT problems and solved using

incremental SAT within a bounded model checking framework, enabling

SRIP to compute shortest reconfiguration sequences efficiently.

We evaluate SRIP on benchmark instances from the CoRe Challenge, a

competition series dedicated to ISRP under TJ. SRIP finds optimal

(shortest) reconfiguration sequences for 477 out of 693 instances,

achieving the best results among state-of-the-art solvers on this

benchmark suite.