<p>You just have to solve the following problem: Find a matching of size exactly $k$ with minimum weight. </p>

<p>It can be solved by reducing to min weight perfect matching. See <a href="http://www.sciencedirect.com/science/article/pii/S0166218X99000529" rel="noreferrer">the paper by Ján Plesnı́k</a>. There is a constant blow up in the number of vertices. So your original problem can be solved in $O(n^3)$ time. </p>

CC BY-SA 3.0
2017-07-30T16:52:06.273Z
Sweet! This works perfectly! I can't up-vote yet, but will when I can!
vincent
CC BY-SA 3.0
2017-07-30T13:38:20.310Z
2017-07-30T13:38:20.310Z
Chao Xu
<p>Given a connected road network on an Island without one-way streets, where should I para-shoot in and what route should I take to deliver mail to all houses on the island (being picked up again by helicopter)?</p>

<p><em>Or in terms of Graphs:</em>
Given an un-directed, connected, weighted Graph, what is the optimal start vertex and shortest path that visits every edge at least once (return to the start vertex not required)?</p>

<p>This question is an altered version of the Route Inspection Problem or Chinese postman problem.</p>

<p>The solution I have working is <code>O(n^5)</code> and I'm trying to improve this.</p>

<p><strong>A Slow-ish Solution</strong></p>

<ul>
<li>First we need to change the graph so that an Eulerian Path exists. We can do this by finding the Minimum Weight, Perfect Matching between all odd vertices (removing <em>two</em> odd vertices since we want a Path and not a Cycle!)</li>
<li>We can use <a href="https://en.wikipedia.org/wiki/Blossom_algorithm" rel="noreferrer">Edmonds' Blossom Algorithm</a> to make the Matching computation efficient. My implementation is currently <code>O(n^3)</code></li>
<li>Adding the computed edges into the Graph ensures an Eulerian Path exists (using the two skipped Vertices as start and end point)</li>
<li>We then compute the Eulerian Path and have an optimal solution for the chosen start and end vertex</li>
</ul>

<p><strong>Question:</strong></p>

<p>The big questions is which two odd vertices to use as the start and end point for the Eulerian Path. So far I am computing all possible Matchings using the Blossom algorithm and taking the one with the minimum weight.</p>

<p>Is there a way that we can do this better? Potentially already integrating it into the Blossom algorithm? Are there any assumptions we can make about the vertices that are optimal? I.e. in a lot of cases two odd vertices with largest distance in the original graph are the best choice, however this is not always true (see Example 3).</p>

<blockquote>
  <p>How can we adjust e.g. this <a href="http://jorisvr.nl/article/maximum-matching" rel="noreferrer">implementation</a> to consider only Matchings of maximum size - 1?</p>
</blockquote>

<p><strong>Example 1</strong></p>

<p>Here is the optimal solution for a maze (the coloring indicates the chosen path). The computation for a given start-end vertex pair is relatively fast (around 100ms). However since this needs to happen for every odd-vertex pair, the overall computation time is over an hour.</p>

<p>There are 278 odd vertices in the maze. Hence we have to compute a Matching <code>(278 * (278 - 1)) / 2 = 38503</code> times.</p>

<p><img src="https://i.sstatic.net/2pS2F.png" alt=""></p>

<p><strong>Example 2</strong></p>

<p>In this example it is obvious that the optimal start and end points are very far apart.</p>

<p><img src="https://i.sstatic.net/YQBTM.png" alt=""></p>

<p><strong>Example 3</strong></p>

<p>The maximal distance between two odd Vertices (the one at the top and the one at the bottom) is 50. However for the optimal path the distance is only 11.</p>

<p><img src="https://i.sstatic.net/kFsB0.png" alt=""></p>

<hr>

<p>PS: Had all the terms nicely linked in the question, but can only include two links due to not having reputation. Oh well...</p>

<ds.algorithms><graph-theory><graph-algorithms><optimization>
Modifying Edmonds' Blossom Algorithm
vincent
# Modifying Edmonds' Blossom Algorithm

(Asked by: username_0 on 2017-07-30)

Given a connected road network on an Island without one-way streets, where should I para-shoot in and what route should I take to deliver mail to all houses on the island (being picked up again by helicopter)?

*Or in terms of Graphs:*
Given an un-directed, connected, weighted Graph, what is the optimal start vertex and shortest path that visits every edge at least once (return to the start vertex not required)?

This question is an altered version of the Route Inspection Problem or Chinese postman problem.

The solution I have working is `O(n^5)` and I'm trying to improve this.

**A Slow-ish Solution**

* First we need to change the graph so that an Eulerian Path exists. We can do this by finding the Minimum Weight, Perfect Matching between all odd vertices (removing *two* odd vertices since we want a Path and not a Cycle!)
* We can use [Edmonds' Blossom Algorithm](https://en.wikipedia.org/wiki/Blossom_algorithm) to make the Matching computation efficient. My implementation is currently `O(n^3)`
* Adding the computed edges into the Graph ensures an Eulerian Path exists (using the two skipped Vertices as start and end point)
* We then compute the Eulerian Path and have an optimal solution for the chosen start and end vertex

**Question:**

The big questions is which two odd vertices to use as the start and end point for the Eulerian Path. So far I am computing all possible Matchings using the Blossom algorithm and taking the one with the minimum weight.

Is there a way that we can do this better? Potentially already integrating it into the Blossom algorithm? Are there any assumptions we can make about the vertices that are optimal? I.e. in a lot of cases two odd vertices with largest distance in the original graph are the best choice, however this is not always true (see Example 3).

> How can we adjust e.g. this [implementation](http://jorisvr.nl/article/maximum-matching) to consider only Matchings of maximum size - 1?

**Example 1**

Here is the optimal solution for a maze (the coloring indicates the chosen path). The computation for a given start-end vertex pair is relatively fast (around 100ms). However since this needs to happen for every odd-vertex pair, the overall computation time is over an hour.

There are 278 odd vertices in the maze. Hence we have to compute a Matching `(278 * (278 - 1)) / 2 = 38503` times.

![](https://i.sstatic.net/2pS2F.png)

**Example 2**

In this example it is obvious that the optimal start and end points are very far apart.

![](https://i.sstatic.net/YQBTM.png)

**Example 3**

The maximal distance between two odd Vertices (the one at the top and the one at the bottom) is 50. However for the optimal path the distance is only 11.

![](https://i.sstatic.net/kFsB0.png)

---

PS: Had all the terms nicely linked in the question, but can only include two links due to not having reputation. Oh well...

**Tags:** ds.algorithms, graph-theory, graph-algorithms, optimization

---

## 1 answers

### Answer by username_1 on 2017-07-30. Score: 7 | Accepted answer

You just have to solve the following problem: Find a matching of size exactly $k$ with minimum weight.

It can be solved by reducing to min weight perfect matching. See [the paper by Ján Plesnı́k](http://www.sciencedirect.com/science/article/pii/S0166218X99000529). There is a constant blow up in the number of vertices. So your original problem can be solved in $O(n^3)$ time.

> **Comments:**
> **username_0**: Sweet! This works perfectly! I can't up-vote yet, but will when I can!  

---

