1
$\begingroup$

Section 2 of this Lecture Note: Shortest Path Algorithms Luis Goddyn, Math 408 describes an algorithm using Edmonds' Minimum Weight Perfect Matching Algorithm to solve the shortest path problem for undirected graphs with negative-weight edges but no negative cycles.

I have two problems in understanding this algorithm:

  • In step 3, why must $G'$ have perfect matchings so that we can apply Edmonds' Minimum Weight Perfect Matching Algorithm to $G'$?
  • In step 4, why must each circuit in $S$ have total weight $0$?
    (A possible argument is like this: Because there are no negative cycles, we only need to show that each circuit in $S$ cannot have positive total weight. Maybe this can be proved by contradiction. Suppose that some circuit in $S$ have positive total weight, we need to show that $M$ is not a mimimum weight perfect matching or this cannot be a circuit. However, I failed to reach a contradiction.)

Related post: Finding shortest paths in undirected graphs with possibly negative edge weights.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

Your answer to the second problem is nice.

Here is an hint or strategy for the first problem.

Select a path $P$ from $s$ to $t$. Verify that there is perfect matching for the corresponding $P'$. Form graph $Q$ from $P$ by adding one vertex $u$ of $G$ not in $P$ (if there is) and all edges from $u$ to vertices in $P$. $P'$ is extended to $Q'$ correspondingly. A bit of reasoning by cases will show the previous perfect matching of $P'$ can be extended to a perfect matching of $Q'$. Now you can add another vertex, repeatedly.

Improve this answer
$\endgroup$
1
$\begingroup$

An answer to the second problem:

Problem: Each circuit in $S$ must have total weight zero. Why?

Proof: By contradiction.
Suppose that some circuit $C$ in $S$ have nonzero total weight.
Because $G$ has no negative cycles, $C$ has positive total weight.
Note that $C$ does not contain $s$ or $t$. Therefore, the edges of $C$ are all $5$-edge gadgets; see step 2.
Then we can construct another perfert matching on $C$ whose total weight is zero by choosing the middle edge with weight $0$ of each $5$-edge gadgets and the edges between $v$ and $v'$ (for each $v$ in $C$; see step 1) also with weight $0$.
This contradicts the assumption that $M$ is a minimum perfect matching.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.