Sliding Token on Bipartite Permutation Graphs

摘要

SLIDING TOKEN is a natural reconfiguration problem in which vertices of independent sets are iteratively replaced by neighbors. We develop techniques that may be useful in answering the conjecture that SLIDING TOKEN is polynomial-time decidable on bipartite graphs. Along the way, we give efficient algorithms for SLIDING TOKEN on bipartite permutation and bipartite distance-hereditary graphs.