Shortest Reconfiguration of Perfect Matchings via Alternating Cycles Motivated by adjacency in perfect matching polytopes, we study the shortest reconfiguration problem of perfect matchings via alternating cycles. Namely, we want to find a shortest sequence of perfect matchings which transforms one given perfect matching to another given perfect matching such that the symmetric difference of each pair of consecutive perfect matchings is a single cycle. The problem is equivalent to the combinatorial shortest path problem in perfect matching polytopes. We prove that the problem is NPhard even when a given graph is planar or bipartite, but it can be solved in polynomial time when the graph is outerplanar.

Fractional matching preclusion number of graphs and the perfect matching polytope Let G be a graph with an even number of vertices. The matching preclusion number of G, denoted by mp(G), is the minimum number of edges whose deletion leaves the resulting graph without a perfect matching. We introduced a 0xe2x80x931 linear program which can be used to find the matching preclusion number of graphs. In this paper, by relaxing of the 0xe2x80x931 linear program we obtain a linear program and call its optimal objective value as fractional matching preclusion number of graph G, denoted by (mp_f(G)). We show (mp_f(G)) can be computed in polynomial time for any graph G. By using the perfect matching polytope, we transform it into a new linear program whose optimal value equals the reciprocal of (mp_f(G)). For bipartite graph G, we obtain an explicit formula for (mp_f(G)) and show that (lfloor mp_f(G) rfloor ) is the maximum integer k such that G has a kfactor. Moreover, for any two bipartite graphs G and H, we show (mp_f(G square H) geqslant mp_f(G)lfloor mp_f(H) rfloor ), where (G square H) is the Cartesian product of G and H.