[2I5-OS-9b] AIと制約プログラミング

[2I5-OS-9b-01] A Study of Solving Dominating Set Reconfiguration Problem with Answer Set Programming

〇Masato Kato¹, Takehide Soh², Naoyuki Tamura³, Mutsunori Banbara¹ (1. Graduate School of Informatics, Nagoya University, 2. Kobe University, Information Infrastructure and Digital Transformation Initiatives Headquarters, 3. Kobe University)

Keywords:Answer Set Programming, Dominating Set Problem, Dominating Set Reconfiguration Problem, Combinatorial Reconfiguration Problem

The Dominating Set Reconfiguration Problem (DSRP) is the problem of determining, for a given dominating set problem and its two feasible solutions, whether one can be reachable to another via a sequence of feasible solutions. Each intermediate solution of the sequence must be generated from its predecessor, subject to some transition constraint. DSRP is known to be PSPACE-complete in general.

In this paper, we describe an approach to solving DSRP based on Answer Set Programming (ASP). The resulting system accepts a DSRP instance and converts it into ASP facts. In turn, these facts are combined with an ASP encoding for DSRP solving, which can subsequently be solved by any off-the-shelf ASP systems, in our case clingo. To evaluate the effectiveness of our approach, we show some experimental results on the third benchmark set of CoRe Challenge 2022.