Gap preserving reductions between reconfiguration problems
From MaRDI portal
Cites work
- A note on succinct representations of graphs
- A Parallel Repetition Theorem
- A survey on the parameterized complexity of reconfiguration problems
- A threshold of ln n for approximating set cover
- Alphabet reduction for reconfiguration problems
- Approximability of the subset sum reconfiguration problem
- Approximating shortest connected graph transformation for trees
- Approximation and hardness of token swapping
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Complexity of independent set reconfigurability problems
- Complexity of token swapping and its variants
- Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
- Explicit construction of linear sized tolerant networks
- Explicit expanders of every degree and size
- Explicit Near-Ramanujan Graphs of Every Degree
- Exponential bounds for DPLL below the satisfiability threshold
- Finding paths between 3-colorings
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Games, puzzles, and computation
- Gap amplification for reconfiguration problems
- Gap Amplification in PCPs Using Lazy Random Walks
- Gap preserving reductions between reconfiguration problems
- scientific article; zbMATH DE number 7272506 (Why is no real title available?)
- scientific article; zbMATH DE number 7803587 (Why is no real title available?)
- Incremental optimization of independent sets under the reconfiguration framework
- Independent-set reconfiguration thresholds of hereditary graph classes
- Introduction to reconfiguration
- Linear degree extractors and the inapproximability of max clique and chromatic number
- On approximate reconfigurability of label cover
- On Dinur’s proof of the PCP theorem
- On the complexity of reconfiguration problems
- On the parameterized complexity of reconfiguration problems
- Optimal PSPACE-hardness of approximating set cover reconfiguration
- Optimization, approximation, and complexity classes
- Parameterized problems complete for nondeterministic FPT time and logarithmic space
- Probabilistic checking of proofs
- Proof verification and the hardness of approximation problems
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- Reconfiguration in bounded bandwidth and tree-depth
- Reconfiguration of graphs with connectivity constraints
- Reconfiguration of list edge-colorings in a graph
- Reconfiguration of spanning trees with degree constraints or diameter constraints
- Reconfiguring shortest paths in graphs
- Shortest Reconfiguration of Colorings Under Kempe Changes
- Shortest reconfiguration of matchings
- Shortest reconfiguration of perfect matchings via alternating cycles
- Some optimal inapproximability results
- Some simplified NP-complete graph problems
- Swapping labeled tokens on graphs
- The complexity of change
- The complexity of dominating set reconfiguration
- The complexity of independent set reconfiguration on bipartite graphs
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
- The PCP theorem by gap amplification
- Token sliding on split graphs
This page was built for publication: Gap preserving reductions between reconfiguration problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6859747)
