The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

DOI10.1137/07070440XzbMath1201.03024OpenAlexW1976090101MaRDI QIDQ5902502

Elitza Maneva, Parikshit Gopalan, Phokion G. Kolaitis, Christos H. Papadimitriou

Publication date: 6 January 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/07070440x

zbMATH Keywords

computational complexitygraph connectivityBoolean satisfiabilityconstraint satisfaction problemPSPACE-completenessdichotomy theoremsgraph of solutionssolution spaces of Boolean formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Connectivity (05C40)

Related Items (67)

On the parameterized complexity of reconfiguration of connected dominating sets ⋮ Multistage vertex cover ⋮ Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ The Complexity of Dominating Set Reconfiguration ⋮ TS-reconfiguration of dominating sets in circle and circular-arc graphs ⋮ Finding shortest paths between graph colourings ⋮ Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ Reconfiguration of dominating sets ⋮ Reconfiguration on nowhere dense graph classes ⋮ Shortest reconfiguration of sliding tokens on subclasses of interval graphs ⋮ Rerouting shortest paths in planar graphs ⋮ Congestion-Free Rerouting of Flows on DAGs ⋮ On the Boolean connectivity problem for Horn relations ⋮ Vertex Cover Reconfiguration and Beyond ⋮ The connectivity of Boolean satisfiability: dichotomies for formulas and circuits ⋮ Finding Shortest Paths Between Graph Colourings ⋮ Reconfiguration of Vertex Covers in a Graph ⋮ The complexity of rerouting shortest paths ⋮ On the Structure of Solution-Graphs for Boolean Formulas ⋮ Token sliding on graphs of girth five ⋮ Reconfiguration in bounded bandwidth and tree-depth ⋮ Recoloring graphs via tree decompositions ⋮ Reconfiguration of Hamiltonian Cycles in Rectangular Grid Graphs ⋮ Reconfiguration of maximum-weight \(b\)-matchings in a graph ⋮ Fast recoloring of sparse graphs ⋮ Token sliding on graphs of girth five ⋮ Mixing is hard for triangle-free reflexive graphs ⋮ Recolouring homomorphisms to triangle-free reflexive graphs ⋮ On the complexity of reconfiguration problems ⋮ Computational complexity of jumping block puzzles ⋮ An exact algorithm for the Boolean connectivity problem for \(k\)-CNF ⋮ Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs ⋮ Complexity of independent set reconfigurability problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Optimal reconfiguration of optimal ladder lotteries ⋮ Shortest Paths between Shortest Paths and Independent Sets ⋮ Approximability of the subset sum reconfiguration problem ⋮ Trichotomy for the reconfiguration problem of integer linear systems ⋮ On girth and the parameterized complexity of token sliding and Token Jumping ⋮ Linear-time algorithm for sliding tokens on trees ⋮ Approximability of the Subset Sum Reconfiguration Problem ⋮ An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree ⋮ Reconfiguring graph homomorphisms on the sphere ⋮ Reconfiguration on sparse graphs ⋮ The complexity of dominating set reconfiguration ⋮ Reconfiguration of list \(L(2,1)\)-labelings in a graph ⋮ On the parameterized complexity of reconfiguration problems ⋮ Reconfiguration of list edge-colorings in a graph ⋮ Shortest paths between shortest paths ⋮ Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect ⋮ Dominating sets reconfiguration under token sliding ⋮ Frozen colourings of bounded degree graphs ⋮ Computational complexity of jumping block puzzles ⋮ Shortest Reconfiguration of Sliding Tokens on a Caterpillar ⋮ Homomorphism Reconfiguration via Homotopy ⋮ Solution-Graphs of Boolean Formulas and Isomorphism ⋮ Reconfiguration of Steiner Trees in an Unweighted Graph ⋮ Independent Set Reconfiguration in Cographs and their Generalizations ⋮ A Reconfigurations Analogue of Brooks' Theorem and Its Consequences ⋮ Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances ⋮ Frozen (Δ + 1)-colourings of bounded degree graphs ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ Introduction to reconfiguration ⋮ Solution-Graphs of Boolean Formulas and Isomorphism1 ⋮ On reconfigurability of target sets

Uses Software

• Walksat

This page was built for publication: The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies