The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

Given a Boolean formula, do its solutions form a connected subgraph of the hypercube? This and other related connectivity considerations underlie recent work on random Boolean satisfiability. We study connectivity properties of the space of solutions of Boolean formulas, and establish computational and structural dichotomies. Specifically, we first establish a dichotomy theorem for the complexity of the st-connectivity problem for Boolean formulas in Schaefer's framework. Our result asserts that the tractable side is more generous than the tractable side in Schaefer's dichotomy theorem for satisfiability, while the intractable side is PSPACE-complete. For the connectivity problem, we establish a dichotomy along the same boundary between membership in coNP and PSPACE-completeness. Furthermore, we establish a structural dichotomy theorem for the diameter of the connected components of the solution space: for the PSPACE-complete cases, the diameter can be exponential, but in all other cases it is linear. Thus, small diameter and tractability of the st-connectivity problem are remarkably aligned.

• Publication year

  2006

• Venue

  SIAM journal on computing (Print)

• Publication date

  2006-07-10

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/07070440XarXiv cs/0609072
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Se p 20 06 The Connectivity of Boolean Satisfiability : Computational and Structural Dichotomies

  2008cited by this paper
• MATHEMATICAL ENGINEERING TECHNICAL REPORTS On the Boolean Connectivity Problem for Horn Relations

  2007cited by this paper
• A Complete Classification of the Complexity of Propositional Abduction

  2006cited by this paper
• On the solution-space geometry of random constraint satisfaction problems

  2006cited by this paper
• Clustering of solutions in the random satisfiability problem

  2005cited by this paper
• Rigorous location of phase transitions in hard optimization problems

  2005cited by this paper
• A new look at survey propagation and its generalizations

  2004cited by this paper
• Playing with Boolean Blocks , Part II : Constraint Satisfaction Problems 1

  2004cited by this paper
• SIGACT news complexity theory column 43

  2004cited by this paper
• Exponential bounds for DPLL below the satisfiability threshold

  2004cited by this paper
• A dichotomy theorem for constraints on a three-element set

  2002cited by this paper
• Random K-satisfiability problem: from an analytic solution to an efficient algorithm.

  2002cited by this paper
• Analytic and Algorithmic Solution of Random Satisfiability Problems

  2002cited by this paper
• The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications

  2002influential reference
• The complexity of minimal satisfiability problems

  2001cited by this paper
• The Approximability of Constraint Satisfaction Problems

  2001cited by this paper
• Complexity classifications of Boolean constraint satisfaction problems

  2001cited by this paper
• Dichotomy Theorem for the Generalized Unique Satisfiability Problem

  1999influential reference
• Complexity of Generalized Satisfiability Counting Problems

  1996cited by this paper
• The Inverse Satisfiability Problem

  1996cited by this paper
• A Dichotomy Theorem for Maximum Generalized Satisfiability Problems

  1995cited by this paper
• Local search strategies for satisfiability testing

  1993cited by this paper
• The complexity of satisfiability problems

  1978influential reference
• On the Structure of Polynomial Time Reducibility

  1975influential reference

• Reconfiguring homomorphisms to reflexive graphs via a simple reduction

  2026cites this paper
• Exact Algorithms and Hardness Result for the Boolean Connectivity Problem of k-Horn Formulas

  2025cites this paper
• Towards an algebraic approach to the reconfiguration CSP

  2025influential citation
• Asymptotically Optimal Inapproximability of Ek-SAT Reconfiguration

  2025influential citation
• PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs

  2025cites this paper
• Yet Another Simple Proof of the PCRP Theorem

  2025cites this paper
• Random Satisfiability Logic-Driven Approach in the Hopfield Neural Networks with Application to COVID-19 Datasets

  2025cites this paper
• A Necessary Condition for Connectedness of Solutions to Integer Linear Systems

  2025cites this paper
• Reconfiguring Proportional Committees

  2025cites this paper
• The tape reconfiguration problem and its consequences for dominating set reconfiguration

  2025cites this paper
• Scalable Hard Instances for Independent Set Reconfiguration

  2024influential citation
• Multi-Winner Reconfiguration

  2024cites this paper
• Reconfiguration of unit squares and disks: PSPACE-hardness in simple settings

  2024cites this paper
• Hardness of approximation for ground state problems

  2024influential citation
• Reconfiguring homomorphisms to reflexive graphs via a simple reduction

  2024cites this paper
• Dominating Set Reconfiguration with Answer Set Programming

  2024cites this paper
• A survey on the parameterized complexity of reconfiguration problems

  2024cites this paper
• Congestion-Free Rerouting of Network Flows: Hardness and an FPT Algorithm

  2024cites this paper
• On Approximate Reconfigurability of Label Cover

  2023cites this paper
• Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems

  2023influential citation
• On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results

  2023cites this paper
• Gap Amplification for Reconfiguration Problems

  2023cites this paper
• Bounded Combinatorial Reconfiguration with Answer Set Programming

  2023cites this paper
• Complexidade parametrizada do problema de reconfiguração de separadores

  2023cites this paper
• Dynamic Debt Swapping in Financial Networks

  2023cites this paper
• A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems

  2022cites this paper
• Gap Preserving Reductions between Reconfiguration Problems

  2022cites this paper
• On The Complexity of Distance-d Independent Set Reconfiguration

  2022cites this paper
• Mixing is hard for triangle-free reflexive graphs

  2022cites this paper
• Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement

  2022cites this paper
• Reconfiguration of Digraph Homomorphisms

  2022cites this paper
• The hamiltonian path graph is connected for simple s, t paths in rectangular grid graphs

  2022cites this paper
• Token Sliding on Graphs of Girth Five

  2022cites this paper
• Shortest reconfiguration of sliding tokens on subclasses of interval graphs

  2021cites this paper
• TS-Reconfiguration of Dominating Sets in circle and circular-arc graphs

  2021cites this paper
• Optimal reconfiguration of optimal ladder lotteries

  2021cites this paper
• Recolouring homomorphisms to triangle-free reflexive graphs

  2021cites this paper
• Reconfiguration Problems on Submodular Functions

  2021cites this paper
• Computational Complexity of Jumping Block Puzzles

  2021cites this paper
• On Reconfigurability of Target Sets

  2021cites this paper
• On reconfiguration graphs: an abstraction

  2021cites this paper
• On Girth and the Parameterized Complexity of Token Sliding and Token Jumping

  2020cites this paper
• WALCOM: Algorithms and Computation: 14th International Conference, WALCOM 2020, Singapore, Singapore, March 31 – April 2, 2020, Proceedings

  2020cites this paper
• Reconfiguration of Hamiltonian cycles and paths in grid graphs

  2020cites this paper
• Frozen (Δ + 1)-colourings of bounded degree graphs

  2020cites this paper
• Some results on Vertex Separator Reconfiguration

  2020cites this paper
• Reconfiguring Hamiltonian Cycles in L-Shaped Grid Graphs

  2019cites this paper
• On the Complexity of Optimal Matching Reconfiguration

  2019cites this paper
• Reconfiguration and combinatorial games

  2019cites this paper
• Dominating sets reconfiguration under token sliding

  2019cites this paper
• 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, Munich, Germany, September 11-13, 2019

  2019cites this paper
• Trichotomy for the reconfiguration problem of integer linear systems

  2019influential citation
• On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets

  2019cites this paper
• Multistage Vertex Cover

  2019cites this paper
• Frozen colourings of bounded degree graphs

  2018cites this paper
• Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect

  2018cites this paper
• Introduction to Reconfiguration

  2018cites this paper
• Congestion-Free Rerouting of Flows on DAGs ∗ 1

  2018cites this paper
• Reconfiguration of maximum-weight b-matchings in a graph

  2018cites this paper
• Shortest Reconfiguration Sequence for Sliding Tokens on Spiders

  2018cites this paper
• Reconfiguring Graph Homomorphisms on the Sphere

  2018cites this paper
• Shortest Reconfiguration of Matchings

  2018cites this paper
• Complexity of Reconfiguration Problems for Constraint Satisfaction

  2018influential citation
• Frozen $(\Delta+1)$-colourings of bounded degree graphs

  2018cites this paper
• D M ] 3 M ar 2 01 5 The complexity of dominating set reconfiguration

  2018cites this paper
• A Generalized Matching Reconfiguration Problem

  2018cites this paper
• The topology of solution spaces of combinatorial problems

  2018cites this paper
• Reconfiguration of Satisfying Assignments for CSP

  2018influential citation
• University of Birmingham Frozen colourings of bounded degree graphs

  2018cites this paper
• Reconfiguration on nowhere dense graph classes

  2017cites this paper
• Introduction to Reconfiguration

  2017influential citation
• Combinatorial Reconfiguration

  2017cites this paper
• Token Jumping in Minor-Closed Classes

  2017cites this paper
• The Complexity of Independent Set Reconfiguration on Bipartite Graphs

  2017cites this paper
• Topics in graph colouring and extremal graph theory

  2016cites this paper
• Tight Exact and Approximate Algorithmic Results on Token Swapping

  2016cites this paper
• Congestion-Free Rerouting of Flows on DAGs

  2016cites this paper
• QCMA hardness of ground space connectivity for commuting Hamiltonians

  2016cites this paper
• Solution-Graphs of Boolean Formulas and Isomorphism

  2016influential citation
• The Complexity of Induced Tree Reconfiguration Problems

  2016cites this paper
• Token Sliding on Chordal Graphs

  2016cites this paper
• Deposited in DRO : 09 November 2015 Version of attached

  2016cites this paper
• Behavior of O(log n) Local Commuting Hamiltonians

  2016cites this paper
• Reconfiguration of Steiner Trees in an Unweighted Graph

  2016cites this paper
• Using contracted solution graphs for solving reconfiguration problems

  2015cites this paper
• Connectivity of Boolean satisfiability

  2015cites this paper
• University of Birmingham Fast recoloring of sparse graphs

  2015cites this paper
• Reconfiguration on Sparse Graphs

  2015cites this paper
• The University Course Timetabling Problem

  2015cites this paper
• Shortest Reconfiguration of Sliding Tokens on a Caterpillar

  2015cites this paper
• Problems: Structure and Tractability

  2015cites this paper
• On Reconfiguration Problems: Structure and Tractability

  2015influential citation
• The complexity of dominating set reconfiguration

  2015cites this paper
• On the Connectedness of Clash-free Timetables

  2015cites this paper
• Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting

  2015cites this paper
• On the Structure of Solution-Graphs for Boolean Formulas

  2015cites this paper
• On the Complexity of Reconfiguration of Clique, Cluster Vertex Deletion, and Dominating Set

  2015influential citation
• Reconfiguration over Tree Decompositions

  2014cites this paper
• Reconfiguration of list L(2,1)-labelings in a graph

  2014cites this paper
• Reconfiguration and structural graph theory

  2014cites this paper