Shortest reconfiguration paths in the solution space of Boolean formulas

DOI10.1007/978-3-662-47672-7_80MaRDI QIDQ3448854zbMATH OpenOpenAlexFDO

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

Publication date 27 October 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: Given a Boolean formula and a satisfying assignment, a flip is an operation that changes the value of a variable in the assignment so that the resulting assignment remains satisfying. We study the problem of computing the shortest sequence of flips (if one exists) that transforms a given satisfying assignment $s$ to another satisfying assignment $t$ of a Boolean formula. Earlier work characterized the complexity of finding any (not necessarily the shortest) sequence of flips from one satisfying assignment to another using Schaefer's framework for classification of Boolean formulas. We build on it to provide a trichotomy for the complexity of finding the shortest sequence of flips and show that it is either in P, NP-complete, or PSPACE-complete. Our result adds to the small set of complexity results known for shortest reconfiguration sequence problems by providing an example where the shortest sequence can be found in polynomial time even though its length is not equal to the symmetric difference of the values of the variables in $s$ and $t$. This is in contrast to all reconfiguration problems studied so far, where polynomial time algorithms for computing the shortest path were known only for cases where the path modified the symmetric difference only.

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
• Media theory. Interdisciplinary applied mathematics.
• On the complexity of reconfiguration problems
• Recoloring graphs via tree decompositions
• Reconfiguration of list edge-colorings in a graph
• Rings of sets
• The complexity of satisfiability problems
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• Transforming triangulations
• Vertex Cover Reconfiguration and Beyond

Cited in

(14)

• Reconfiguration on nowhere dense graph classes
• On girth and the parameterized complexity of token sliding and token jumping
• Introduction to reconfiguration
• Rerouting shortest paths in planar graphs
• The connectivity of Boolean satisfiability: dichotomies for formulas and circuits
• Shortest reconfiguration of sliding tokens on subclasses of interval graphs
• Shortest Reconfiguration of Sliding Tokens on a Caterpillar
• Reconfiguration of Steiner trees in an unweighted graph
• The complexity of dominating set reconfiguration
• Shortest reconfiguration paths in the solution space of Boolean formulas
• scientific article; zbMATH DE number 7765402 (Why is no real title available?)
• scientific article; zbMATH DE number 7764115 (Why is no real title available?)
• Some results on vertex separator reconfiguration
• On the parameterized complexity of reconfiguration of connected dominating sets

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 Q3448854)