Reconfiguring homomorphisms to reflexive graphs via a simple reduction
This paper studies the problem of changing one graph homomorphism into another by recoloring one vertex at a time, while always keeping a valid homomorphism. The authors focus on the case where the target graph \(H\) is reflexive (every vertex has a loop). They give a simple reduction that converts this problem into a similar problem for a related bipartite graph built from the maximal cliques of \(H\). Using this idea, they prove that if \(H\) is reflexive and square-free, then the recoloring problem can be solved in polynomial time.\N\NAlthough the full complexity classification of the problem is still open, this work gives an important step forward and provides useful tools for future research.
- A computational trichotomy for connectivity of Boolean satisfiability
- A dichotomy theorem for nonuniform CSPs
- A proof of the CSP dichotomy conjecture
- Finding paths between 3-colorings
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Gibbs measures and dismantlable graphs
- Homomorphism reconfiguration via homotopy
- Mixing is hard for triangle-free reflexive graphs
- On the complexity of H-coloring
- Recolouring homomorphisms to triangle-free reflexive graphs
- Reconfiguration of digraph homomorphisms
- Reconfiguring graph homomorphisms on the sphere
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
This page was built for publication: Reconfiguring homomorphisms to reflexive graphs via a simple reduction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6866273)
