Shortest reconfiguration paths in the solution space of Boolean formulas

DOI10.1137/16M1065288MaRDI QIDQ5361235zbMATH OpenFDO

Authors Amer E. Mouawad, N. Nishimura, Vinayak Pathak, Venkatesh Raman

Publication date 27 September 2017

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

Full work available at URL https://doi.org/10.1137/16M1065288

zbMATH Keywords

Boolean formulasreconfigurationsatisfiabilitysolution space

Mathematics Subject Classification ID

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

Recommendations

• Shortest reconfiguration paths in the solution space of Boolean formulas
• The connectivity of Boolean satisfiability: dichotomies for formulas and circuits
• The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT

Cites work

• -graphs of graphs
• A computational trichotomy for connectivity of Boolean satisfiability
• A note on some tree similarity measures
• Complexity classifications of Boolean constraint satisfaction problems
• Complexity of independent set reconfigurability problems
• Computational Complexity
• Connectedness of the graph of vertex-colourings
• Distance labeling in graphs (extended abstract)
• Finding shortest paths between graph colourings
• Fixed-parameter tractability of token jumping on planar graphs
• Media theory. Interdisciplinary applied mathematics.
• On the complexity of reconfiguration problems
• On the Parameterized Complexity for Token Jumping on Graphs
• Proximity-preserving labeling schemes
• Reconfiguration of list edge-colorings in a graph
• Reconfiguration over tree decompositions
• Rings of sets
• Shortest reconfiguration paths in the solution space of Boolean formulas
• The complexity of bounded length graph recoloring and CSP reconfiguration
• The complexity of change
• The complexity of satisfiability problems
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• Transforming triangulations
• Vertex Cover Reconfiguration and Beyond

Cited in

(18)

• Dominating sets reconfiguration under token sliding
• On reconfigurability of target sets
• Optimal reconfiguration of optimal ladder lotteries
• Using contracted solution graphs for solving reconfiguration problems
• Reconfiguration of maximum-weight b-matchings in a graph
• Shortest reconfiguration paths in the solution space of Boolean formulas
• Shortest reconfiguration of perfect matchings via alternating cycles
• Homomorphism reconfiguration via homotopy
• Token sliding on graphs of girth five
• Token sliding on graphs of girth five
• Hamiltonian cycle reconfiguration with answer set programming
• Recongo: bounded combinatorial reconfiguration with answer set programming
• Combinatorial reconfiguration with answer set programming: algorithms, encodings, and empirical analysis
• Reconfiguring shortest paths in graphs
• Optimal PSPACE-hardness of approximating set cover reconfiguration
• Reconfiguration using generalized token jumping
• A survey on the parameterized complexity of reconfiguration problems
• The tape reconfiguration problem and its consequences for dominating set reconfiguration

This page was built for publication: Shortest reconfiguration paths in the solution space of Boolean formulas

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