Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas

DOI10.1137/16M1065288zbMath1374.68247MaRDI QIDQ5361235

Venkatesh Raman, Naomi Nishimura, Amer E. Mouawad, Vinayak Pathak

Publication date: 27 September 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

solution spacesatisfiabilityreconfigurationBoolean formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (9)

Shortest Reconfiguration of Perfect Matchings via Alternating Cycles ⋮ Token sliding on graphs of girth five ⋮ Reconfiguration of maximum-weight \(b\)-matchings in a graph ⋮ Token sliding on graphs of girth five ⋮ Optimal reconfiguration of optimal ladder lotteries ⋮ Dominating sets reconfiguration under token sliding ⋮ Homomorphism Reconfiguration via Homotopy ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ On reconfigurability of target sets

Cites Work

• Complexity of independent set reconfigurability problems
• On the parameterized complexity of reconfiguration problems
• On the complexity of reconfiguration problems
• Reconfiguration of list edge-colorings in a graph
• Flip distance between triangulations of a simple polygon is NP-complete
• A note on some tree similarity measures
• Reconfiguration on sparse graphs
• Connectedness of the graph of vertex-colourings
• Transforming triangulations
• Rings of sets
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• The complexity of change
• Fixed-Parameter Tractability of Token Jumping on Planar Graphs
• Vertex Cover Reconfiguration and Beyond
• The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
• Finding Shortest Paths Between Graph Colourings
• Reconfiguration over Tree Decompositions
• γ-graphs of graphs
• Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas
• Proximity-preserving labeling schemes
• Computational Complexity
• The complexity of satisfiability problems
• On the Parameterized Complexity for Token Jumping on Graphs
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas