4
$\begingroup$

The Eulerian Tour problem is of course a well-studied classical problem in graph theory (Wikipedia article). 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)?

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Suresh Venkat Jan 7 '13 at 21:16
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Great, that seems to be what I had in mind. $\endgroup$ – MCH Jan 7 '13 at 22:47

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.