<p>For total cost, see <a href="http://en.wikipedia.org/wiki/Route_inspection_problem">http://en.wikipedia.org/wiki/Route_inspection_problem</a> (also called the Chinese postman problem). The optimal solutions to this problem visit each edge at most twice, so they also optimize your width cost.</p>

CC BY-SA 3.0
2013-01-07T22:47:13.503Z
Great, that seems to be what I had in mind.
Mahdi Cheraghchi
CC BY-SA 3.0
2013-01-07T21:50:37.097Z
2013-01-07T21:50:37.097Z
David Eppstein
<p>The <em>Eulerian Tour</em> problem is of course a well-studied classical problem in graph theory (<a href="http://en.wikipedia.org/wiki/Eulerian_path" rel="nofollow">Wikipedia article</a>). This question concerns non-Eulerian graphs; i.e., graphs that contain one or more odd-degree vertices. In a nutshell, I wonder what is the best "Eulerian-like" way of traversing non-Eulerian graphs.</p>

<p>Given an undirected connected graph, let an Eulerian "semi-tour" be defined as a "cycle" that passes each edge <em>at least</em> once and can visit any vertex or edge multiple times. Consider the following costs for a given semi-tour:</p>

<ol>
<li><p>Total cost: The total number of edges visited by the semi-tour, counting multiplicities.</p></li>
<li><p>Width cost: The number of times the most-visited edge is visited.</p></li>
</ol>

<p>I'm interested in optimization problems that aim to find a semi-tour that minimizes the total cost or the width cost on a given graph. Of course, if a graph is Eulerian, an Eulerian tour would be optimal, for which the total cost is the number of edges and the width cost is zero. For graphs containing odd degree vertices, the optimal cost in both senses must be larger.</p>

<p>I suspect these optimization problems (if not trivial) must have been well studied in the literature. What are the relevant references, if any, and what is known about these problems (both algorithmically and combinatorially)?</p>

CC BY-SA 3.0
2013-01-07T21:16:05.233Z
I wonder what happens if you do the Christofides trick: find a "min congestion matching" on the odd degree vertices and then run the Euler tour
Suresh Venkat
<graph-theory><co.combinatorics><optimization>
Nearly-Eulerian Tours
Mahdi Cheraghchi
# Nearly-Eulerian Tours

(Asked by: username_0 on 2013-01-07)

The *Eulerian Tour* problem is of course a well-studied classical problem in graph theory ([Wikipedia article](http://en.wikipedia.org/wiki/Eulerian_path)). This question concerns non-Eulerian graphs; i.e., graphs that contain one or more odd-degree vertices. In a nutshell, I wonder what is the best "Eulerian-like" way of traversing non-Eulerian graphs.

Given an undirected connected graph, let an Eulerian "semi-tour" be defined as a "cycle" that passes each edge *at least* once and can visit any vertex or edge multiple times. Consider the following costs for a given semi-tour:

1. Total cost: The total number of edges visited by the semi-tour, counting multiplicities.
2. Width cost: The number of times the most-visited edge is visited.

I'm interested in optimization problems that aim to find a semi-tour that minimizes the total cost or the width cost on a given graph. Of course, if a graph is Eulerian, an Eulerian tour would be optimal, for which the total cost is the number of edges and the width cost is zero. For graphs containing odd degree vertices, the optimal cost in both senses must be larger.

I suspect these optimization problems (if not trivial) must have been well studied in the literature. What are the relevant references, if any, and what is known about these problems (both algorithmically and combinatorially)?

**Tags:** graph-theory, co.combinatorics, optimization

> **Comments:**
> **username_1**: I wonder what happens if you do the Christofides trick: find a "min congestion matching" on the odd degree vertices and then run the Euler tour  

---

## 1 answers

### Answer by username_2 on 2013-01-07. Score: 9 | Accepted answer

For total cost, see <http://en.wikipedia.org/wiki/Route_inspection_problem> (also called the Chinese postman problem). The optimal solutions to this problem visit each edge at most twice, so they also optimize your width cost.

> **Comments:**
> **username_0**: Great, that seems to be what I had in mind.  

---

