Dominating Set Reconfiguration with Answer Set Programming
Open Access
- 1 July 2024
- journal article
- research article
- Published by Cambridge University Press (CUP) in Theory and Practice of Logic Programming
- Vol. 24 (4) , 755-771
Abstract
The dominating set reconfiguration problem is defined as determining, for a given dominating set problem and two among its feasible solutions, whether one is reachable from the other via a sequence of feasible solutions subject to a certain adjacency relation. This problem is PSPACE-complete in general. The concept of the dominating set is known to be quite useful for analyzing wireless networks, social networks, and sensor networks. We develop an approach to solve the dominating set reconfiguration problem based on answer set programming (ASP). Our declarative approach relies on a high-level ASP encoding, and both the grounding and solving tasks are delegated to an ASP-based combinatorial reconfiguration solver. To evaluate the effectiveness of our approach, we conduct experiments on a newly created benchmark set.Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- Combinatorial Reconfiguration with Answer Set Programming: Algorithms, Encodings, and Empirical Analysis2024
- Recongo: Bounded Combinatorial Reconfiguration with Answer Set Programming2023
- Hamiltonian Cycle Reconfiguration with Answer Set Programming2023
- ZDD-Based Algorithmic Framework for Solving Shortest Reconfiguration Problems2023
- Dominating sets reconfiguration under token slidingDiscrete Applied Mathematics, 2021
- Reconfiguration of dominating setsJournal of Combinatorial Optimization, 2015
- The k-Dominating GraphGraphs and Combinatorics, 2013
- Finding paths between 3-coloringsJournal of Graph Theory, 2010
- The Second Answer Set Programming Competition2009
- Connected Dominating Set in Sensor Networks and MANETs2006