# For each edge, find a matching that containing it and has maximum weight

Given a weighted graph $G=(V,E)$. For each edge $e\in E$, we are interested in finding a maximum weight matching over all matchings that contains edge $e$.

If $G$ is bipartite, then this can be done in $O(n^3)$ time:

1. Apply the standard reduction to min-cost flow.

2. Find a min-cost flow.

3. Compute all-pairs shortest path in the residual graph, and use the augmenting paths to extract the desired matchings.

Is there an $O(n^3)$ time algorithm in general graphs?