The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
From MaRDI portal
Boolean satisfiabilitycomputational complexityconstraint satisfaction problemdichotomy theoremsgraph connectivitygraph of solutionsPSPACE-completenesssolution spaces of Boolean formulas
Classical propositional logic (03B05) Complexity of computation (including implicit computational complexity) (03D15) Connectivity (05C40) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)
Recommendations
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
- The connectivity of Boolean satisfiability: dichotomies for formulas and circuits
- The Connectivity of Boolean Satisfiability: Dichotomies for Formulas and Circuits
- A computational trichotomy for connectivity of Boolean satisfiability
- On the structure of Boolean satisfiability
- Bridging constraint satisfaction and Boolean satisfiability
- On the Boolean connectivity problem for Horn relations
- On the Boolean Connectivity Problem for Horn Relations
- scientific article; zbMATH DE number 1630006
- On the structure of solution-graphs for Boolean formulas
Cited in
(89)- 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
- Frozen colourings of bounded degree graphs
- The complexity of minimal satisfiability problems
- 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
- Finding shortest paths between graph colourings
- A computational trichotomy for connectivity of Boolean satisfiability
- Shortest reconfiguration paths in the solution space of Boolean formulas
- The complexity of dominating set reconfiguration
- On the Boolean Connectivity Problem for Horn Relations
- The complexity of rerouting shortest paths
- Complexity of independent set reconfigurability problems
- Approximability of the subset sum reconfiguration problem
- An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
- Linear-time algorithm for sliding tokens on trees
- The Connectivity of Boolean Satisfiability: Dichotomies for Formulas and Circuits
- Frozen (+1)-colourings of bounded degree graphs
- Congestion-free rerouting of flows on DAGs
- Solution-Graphs of Boolean Formulas and Isomorphism1
- On reconfiguration graphs: an abstraction
- The complexity of dominating set reconfiguration
- Homomorphism reconfiguration via homotopy
- Shortest reconfiguration paths in the solution space of Boolean formulas
- Equivalence of strongly connected graphs and black-and-white 2-SAT problems
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
- Token sliding on graphs of girth five
- Reconfiguration of Hamiltonian Cycles in Rectangular Grid Graphs
- On the Boolean connectivity problem for Horn relations
- scientific article; zbMATH DE number 7765402 (Why is no real title available?)
- scientific article; zbMATH DE number 7764115 (Why is no real title available?)
- Computational complexity of jumping block puzzles
- Mixing is hard for triangle-free reflexive graphs
- Token sliding on graphs of girth five
- On the complexity of reconfiguration problems
- An exact algorithm for the Boolean connectivity problem for k-CNF
- Computational complexity of puzzles and related topics
- 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
- On connectedness of solutions to integer linear systems
- The Hamiltonian path graph is connected for simple s,t paths in rectangular grid graphs
- Dynamic debt swapping in financial networks
- Gap preserving reductions between reconfiguration problems
- Reconfiguring homomorphisms to reflexive graphs via a simple reduction
- Algorithms for burning schedule reconfiguration problem on path forests
- Optimal PSPACE-hardness of approximating set cover reconfiguration
- Some results on vertex separator reconfiguration
- On approximate reconfigurability of label cover
- A survey on the parameterized complexity of reconfiguration problems
- Reconfiguration of digraph homomorphisms
- Reconfiguration of list edge-colorings in a graph
- Shortest paths between shortest paths
- A generalized matching reconfiguration problem
- Optimal list recoloring of subcubic graphs and complete multipartite graphs
- Reconfiguration of unit squares and disks: PSPACE-hardness in simple settings
- The tape reconfiguration problem and its consequences for dominating set reconfiguration
- On the parameterized complexity of reconfiguration of connected dominating sets
- Fast recoloring of sparse graphs
- The Helly property and satisfiability of Boolean formulas defined on set families
This page was built for publication: The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5902502)
