Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect
DOI10.1007/978-3-319-94776-1_31zbMath1436.68132arXiv1805.04055OpenAlexW2799572506WikidataQ127581171 ScholiaQ127581171MaRDI QIDQ5916254
Andrew Winslow, Erik D. Demaine, Robert A. Hearn, David Eppstein, Jean Cardinal
Publication date: 4 October 2018
Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1805.04055
computational complexityBoolean satisfiabilityPSPACE-completenesssubset sumreconfigurationcombinatorial reconfigurationsubset sum problem
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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 Boolean connectivity problem for Horn relations
- An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
- Reconfiguration of list edge-colorings in a graph
- Shortest paths between shortest paths
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Reconfiguration in bounded bandwidth and tree-depth
- Introduction to reconfiguration
- Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
- Relationships between nondeterministic and deterministic tape complexities
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- Reconfiguration of Steiner Trees in an Unweighted Graph
- Independent Set Reconfiguration in Cographs and their Generalizations
- The complexity of change
- The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
- On the Structure of Solution-Graphs for Boolean Formulas
- Finding paths between 3-colorings
- Reconfiguring Independent Sets in Claw-Free Graphs
- Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas
- On the complexity of integer programming
- Planar Formulae and Their Uses
- The Complexity of Independent Set Reconfiguration on Bipartite Graphs
- Sliding Tokens on a Cactus
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
