ABSTRACT
In graph theory, reconfiguration is concerned with relationships among solutions to a given problem for a specific graph. The reconfiguration of one solution into another occurs via a sequence of steps, defined according to a predetermined rule, such that each step produces an intermediate solution to the problem. The solutions form the vertex set of the associated reconfiguration graph, two vertices being adjacent if one solution can be obtained from the other in a single step. Exact counting of 172combinatorial structures is seldom possible in polynomial time. Approximate counting of the structures, however, may be possible. When the reconfiguration graph associated with a specific structure is connected, Markov chain simulation can be used to achieve approximate counting. Typical questions about the reconfiguration graph therefore concern its structure (connectedness, * Hamiltonicity, diameter, planarity), realisability (which graphs can be realised as a specific type of reconfiguration graph), and algorithmic properties (finding shortest paths between solutions quickly).
