2
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.