Homomorphism Reconfiguration via Homotopy
From MaRDI portal
Publication:5212954
DOI10.1137/17M1122578zbMath1448.68249MaRDI QIDQ5212954
Publication date: 31 January 2020
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of simplicial complexes (05E45)
Related Items (6)
Topology and Adjunction in Promise Constraint Satisfaction ⋮ Token sliding on graphs of girth five ⋮ Token sliding on graphs of girth five ⋮ Recolouring homomorphisms to triangle-free reflexive graphs ⋮ Homomorphism complexes, reconfiguration, and homotopy for directed graphs ⋮ Dismantlability, connectedness, and mixing in relational structures
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A dichotomy theorem for circular colouring reconfiguration
- Finding shortest paths between graph colourings
- Complexity of independent set reconfigurability problems
- Foldings in graphs and relations with simplicial complexes and posets
- Induced subgraphs of graphs with large chromatic number. IV: Consecutive holes
- Hom complexes and homotopy theory in the category of graphs
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- On the complexity of H-coloring
- Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
- Graphs with a cycle of length divisible by three
- Reconfiguration in bounded bandwidth and tree-depth
- Proof of the Kalai-Meshulam conjecture
- Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue
- Complexes of graph homomorphisms
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- Proof equivalence in MLL is PSPACE-complete
- The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
- Four-cycle free graphs, height functions, the pivot property and entropy minimality
- Finding paths between 3-colorings
- Reconfiguring Independent Sets in Claw-Free Graphs
- Random subgroups and analysis of the length-based and quotient attacks
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The Connectivity of Boolean Satisfiability: Dichotomies for Formulas and Circuits
- Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas
- The complexity of satisfiability problems
- On the solution‐space geometry of random constraint satisfaction problems
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
This page was built for publication: Homomorphism Reconfiguration via Homotopy
