2026-08-07T12:10:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20391 2024-07-11T07:11:32Z ddc:004 open_access

Scalable Hard Instances for Independent Set Reconfiguration Soh, Takehide Watanabe, Takumu Kawahara, Jun Suzuki, Akira Ito, Takehiro Combinatorial reconfiguration Benckmark dataset Graph Algorithm PSPACE-complete The Token Jumping problem, also known as the independent set reconfiguration problem under the token jumping model, is defined as follows: Given a graph and two same-sized independent sets, determine whether one can be transformed into the other via a sequence of independent sets. Token Jumping has been extensively studied, mainly from the viewpoint of algorithmic theory, but its practical study has just begun. To develop a practically good solver, it is important to construct benchmark datasets that are scalable and hard. Here, "scalable" means the ability to change the scale of the instance while maintaining its characteristics by adjusting the given parameters; and "hard" means that the instance can become so difficult that it cannot be solved within a practical time frame by a solver. In this paper, we propose four types of instance series for Token Jumping. Our instance series is scalable in the sense that instance scales are controlled by the number of vertices. To establish their hardness, we focus on the numbers of transformation steps; our instance series requires exponential numbers of steps with respect to the number of vertices. Interestingly, three types of instance series are constructed by importing theories developed by algorithmic research. We experimentally evaluate the scalability and hardness of the proposed instance series, using the SAT solver and award-winning solvers of the international competition for Token Jumping. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Takehide Soh and Takumu Watanabe and Jun Kawahara and Akira Suzuki and Takehiro Ito 2024 Is Part Of LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2024.26 urn:nbn:de:0030-drops-203913 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.26 eng https://creativecommons.org/licenses/by/4.0/legalcode