The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
From MaRDI portal
Publication:5902502
DOI10.1137/07070440XzbMath1201.03024MaRDI 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
computational complexity; graph connectivity; Boolean satisfiability; constraint satisfaction problem; PSPACE-completeness; dichotomy theorems; graph of solutions; solution spaces of Boolean formulas
68Q25: Analysis of algorithms and problem complexity
03D15: Complexity of computation (including implicit computational complexity)
03B05: Classical propositional logic
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
05C40: Connectivity
Related Items
Unnamed Item, Frozen (Δ + 1)-colourings of bounded degree graphs, Solution-Graphs of Boolean Formulas and Isomorphism1, Congestion-Free Rerouting of Flows on DAGs, Homomorphism Reconfiguration via Homotopy, Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas, Trichotomy for the reconfiguration problem of integer linear systems, Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect, Unnamed Item, Unnamed Item, Computational complexity of jumping block puzzles, Token sliding on graphs of girth five, Reconfiguration of Hamiltonian Cycles in Rectangular Grid Graphs, Token sliding on graphs of girth five, Mixing is hard for triangle-free reflexive graphs, Finding shortest paths between graph colourings, Reconfiguration of dominating sets, The complexity of rerouting shortest paths, Complexity of independent set reconfigurability problems, Approximability of the subset sum reconfiguration problem, Linear-time algorithm for sliding tokens on trees, The complexity of dominating set reconfiguration, On the parameterized complexity of reconfiguration problems, On the Boolean connectivity problem for Horn relations, On the complexity of reconfiguration problems, An exact algorithm for the Boolean connectivity problem for \(k\)-CNF, Reconfiguration of list edge-colorings in a graph, Shortest paths between shortest paths, On the parameterized complexity of reconfiguration of connected dominating sets, Fast recoloring of sparse graphs, Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances, Reconfiguration on nowhere dense graph classes, Reconfiguration in bounded bandwidth and tree-depth, Recoloring graphs via tree decompositions, Reconfiguration on sparse graphs, Frozen colourings of bounded degree graphs, On girth and the parameterized complexity of token sliding and Token Jumping, Reconfiguring graph homomorphisms on the sphere, Dominating sets reconfiguration under token sliding, On reconfigurability of target sets, Multistage vertex cover, TS-reconfiguration of dominating sets in circle and circular-arc graphs, Optimal reconfiguration of optimal ladder lotteries, Reconfiguration of list \(L(2,1)\)-labelings in a graph, Using contracted solution graphs for solving reconfiguration problems, Introduction to reconfiguration, Rerouting shortest paths in planar graphs, The connectivity of Boolean satisfiability: dichotomies for formulas and circuits, Reconfiguration of maximum-weight \(b\)-matchings in a graph, Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs, Shortest reconfiguration of sliding tokens on subclasses of interval graphs, Recolouring homomorphisms to triangle-free reflexive graphs, Computational complexity of jumping block puzzles, Shortest Reconfiguration of Sliding Tokens on a Caterpillar, 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, Vertex Cover Reconfiguration and Beyond, Finding Shortest Paths Between Graph Colourings, Reconfiguration of Vertex Covers in a Graph, On the Structure of Solution-Graphs for Boolean Formulas, Shortest Paths between Shortest Paths and Independent Sets, Approximability of the Subset Sum Reconfiguration Problem, An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree, Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas, The Complexity of Dominating Set Reconfiguration
Uses Software
