ZDD-based algorithmic framework for solving shortest reconfiguration problems

DOI10.1007/978-3-031-33271-5_12arXiv2207.13959OpenAlexW4377249480MaRDI QIDQ6057258FDOQ6057258

Authors: Takehiro Ito, Jun Kawahara, Yu Nakahata, Takehide Soh, Akira Suzuki, Junichi Teruyama, Takahisa Toda 

Publication date: 4 October 2023

Published in: Integration of Constraint Programming, Artificial Intelligence, and Operations Research (Search for Journal in Brave)

Abstract: This paper proposes an algorithmic framework for various reconfiguration problems using zero-suppressed binary decision diagrams (ZDDs), a data structure for families of sets. In general, a reconfiguration problem checks if there is a step-by-step transformation between two given feasible solutions (e.g., independent sets of an input graph) of a fixed search problem such that all intermediate results are also feasible and each step obeys a fixed reconfiguration rule (e.g., adding/removing a single vertex to/from an independent set). The solution space formed by all feasible solutions can be exponential in the input size, and indeed many reconfiguration problems are known to be PSPACE-complete. This paper shows that an algorithm in the proposed framework efficiently conducts the breadth-first search by compressing the solution space using ZDDs, and finds a shortest transformation between two given feasible solutions if exists. Moreover, the proposed framework provides rich information on the solution space, such as the connectivity of the solution space and all feasible solutions reachable from a specified one. We demonstrate that the proposed framework can be applied to various reconfiguration problems, and experimentally evaluate their performances.

Full work available at URL: https://arxiv.org/abs/2207.13959

zbMATH Keywords

graph algorithmsbinary decision diagramscombinatorial reconfiguration

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Combinatorial optimization (90C27) Operations research and management science (90Bxx)

Cites Work

• Graph-Based Algorithms for Boolean Function Manipulation
• The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
• Title not available (Why is that?)
• Connectedness of the graph of vertex-colourings
• The complexity of change
• Computing the Tutte polynomial of a graph of moderate size
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Complexity of independent set reconfigurability problems
• On the complexity of reconfiguration problems
• Decision Diagrams for Discrete Optimization: A Survey of Recent Advances
• Implicit enumeration of topological-minor-embeddings and its application to planar subgraph enumeration
• Introduction to reconfiguration
• Reconfiguration of connected graph partitions
• Distributed reconfiguration of maximal independent sets
• Output-size sensitiveness of OBDD construction through maximal independent set problem

Cited In (2)

• Combinatorial reconfiguration with answer set programming: algorithms, encodings, and empirical analysis
• ZODIAC—an algorithm for concurrent formation of part-families and machine-cells

This page was built for publication: ZDD-based algorithmic framework for solving shortest reconfiguration problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6057258)