Barriers in Matching Reconfiguration: Exact Guided Depth in Odd Prisms

We introduce a structural framework for the reconfiguration complexity of perfect matchings in matching-covered graphs, governed by a barrier invariant that measures the separation between symmetric-dierence components. As the rst complete case study, we determine the exact monotone guided depth of odd prisms: for the odd prism P2k+1 = C2k+1□K2, we exhibit a canonical family of matching pairs whose monotone guided depth is exactly k−1 = diam(P2k+1)−2. The upper bound is achieved by explicit slide and merge alternating cycles. The lower bound relies on ve ladder-local forcing lemmas exploiting the degree-3 structure: directed zigzag propagation (any alternating cycle visiting a shared-rung column must use the rung and propagate locally), single entry/exit (at most one shared rung per ip on any gap arc, for guided leak ips), merge obstruction (merging is impossible while any separating arc contains shared rungs), two-sided elimination (ips touching both components -create too many new components), and one-sided classication (the only φ-preserving one-sided ips are slides). We further conjecture, with exhaustive computational evidence for small cases, that allowing component splits does not reduce the guided depth. As consequences, the guided depth is unbounded and grows linearly in the diameter. We propose the barrier count β as a general invariant governing reconguration complexity and formulate a hierarchy of conjectures for matching-covered graphs.