22 citations · 107 across the 16 of their papers we have counts for
4 papers · 1 filter
Homomorphism reconfiguration via homotopy
Marcin Wrochna
We consider the following problem for a fixed graph H: given a graph G and two H-colorings of G, i.e. homomorphisms from G to H, can one be transformed (reconfigured) into the othe…
Reconfiguration in bounded bandwidth and treedepth
Marcin Wrochna
We show that several reconfiguration problems known to be PSPACE-complete remain so even when limited to graphs of bounded bandwidth. The essential step is noticing the similarity…
Reconfiguration over tree decompositions
Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman +1
A vertex-subset graph problem defines which subsets of the vertices of an input graph are feasible solutions. The reconfiguration version of a vertex-subset problem asks wh…
Reconfiguring Independent Sets in Claw-Free Graphs
Paul Bonsma, Marcin Kamiński, Marcin Wrochna
We present a polynomial-time algorithm that, given two independent sets in a claw-free graph , decides whether one can be transformed into the other by a sequence of elementary…