ZDD-based algorithmic framework for solving shortest reconfiguration problems

DOI10.1007/978-3-031-33271-5_12MaRDI QIDQ6057258zbMATH OpenOpenAlexFDO

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)

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)

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.

Cites work

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

Cited in

(2)

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

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)