[Solved]: Is there a non-brute force algorithm for Eulerization of graphs?

Problem Detail: 

Given some undirected, unweighted, connected, and potentially parallel-edged graph $G$, an Euler circuit may be constructed iff every vertex in $G$ has an even degree.

In graphs with two or more vertices of odd degree (there may only be multiples of two), one must "Eulerize" the graph, connecting the odd vertices with additional edges through other vertices if necessary.

The optimal case for Eulerization is with the construction of only $n/2$ edges, where $n$ is the number of odd degree vertices, but this can only be the case if each odd vertex has an adjacent partner, thus allowing us to connect both vertices with one edge and making them both even.

That being said, most graphs will require more than $n/2$ edges. As humans, we tend to Eulerize graphs by always choosing each pair of odd vertices that are adjacent to one another, and then using trial and error for the rest. However, this does not always work.

For instance, in the following graph, choosing to add an edge between the pair of adjacent odd vertices, $1\leftrightarrow 2$ and using $5$ edges to connect $3\leftrightarrow 4$ results in an Eulerization that costs $6$ edges. However, choosing to instead connect $1\leftrightarrow 4$ and $2\leftrightarrow 3$ yields an Eulerization that costs $5$ edges, even though it did not use the adjacent odd vertices to its advantage.

I know for sure that this problem is solvable, at least by brute force, because the number of pairs of odd vertices which should be connected with some number of edges is finite; specifically, there are $2^{n/2} \Gamma(\frac{n+1}{2})/\sqrt{\pi}$ (Mathematica said so) possible sets of pairs of odd vertices to connect. It's possible to go through each one, linking up each vertex to its partner (finding the shortest path between the two vertices in an undirected graph is probably a challenge within itself, which Wikipedia fails to give a time complexity for).

In the end, the whole deal probably runs in polynomial times exponential times factorial time, which is pretty nasty. I've done some basic research into whether there are algorithms which Eulerize paths, but can't seem to find any.

Mathematica code for graphic:

GraphPlot[   {1 -> 2, 2 -> 5, 5 -> 3, 3 -> 6, 6 -> 3, 6 -> 7, 7 -> 6, 2 -> 7, 7 -> 8, 8 -> 9, 9 -> 10, 10 -> 4, 4 -> 11, 11 -> 4, 11 -> 12, 12 -> 1, 1 -> 12},    VertexRenderingFunction ->      (If[#2 < 5,          Text[Style[#2, Large], #1, Background -> Yellow], Null] &)] 

Asked By : VF1

Answered By : Paresh

Consider the Chinese Postman Problem on undirected graphs: Given an undirected graph $G$, find the shortest circuit of the graph that travels every edge atleast once. Now, if $G$ is Eulerian, then the Euler circuit is the shortest such circuit. If not, some edges will be traveled more than once. In other words, some edges will be duplicated, and the circuit will be Eulerian on the graph with these extra edges.

Now, for obtaining the shortest circuit, the edge duplication has to be minimized. This is the same as your problem. You need to find a new graph $H$ which has all the edges of $G$, and a few extra parallel edges - as few extra edges as possible - so that $H$ is Eulerian. Each extra edge in $H$ corresponds to the fact that its corresponding parallel edge in $G$ is visited again in a shortest complete circuit of $G$. In other words, the optimum (minimal) "eulerization" is equivalent to the Chinese Postman problem. For a better expressed explanation of this, refer to Section 4 (Chinese Postman Problem) and Definition 11 (Eulerization, Minimal Eulerization) of these notes. Fortunately, this is solvable in polynomial time for undirected graphs.

For the Chinese Postman problem, Wikipedia has one solution. I describe another algorithm from Steven Skiena's The Algorithm Design Manual [1]:

1. Find the shortest paths between each pair of odd-degree vertices in $G$: $O(n^3)$.
2. Finding the best set of shortest paths to add to $G$ reduces to identifying the minimum-weight perfect matching in a special graph $G' = (V', E')$. The vertices $V'$ of $G'$ correspond the odd-degree vertices of $G$, with the weight of the edge $(i, j) \in E'$ defined to be the length of the shortest path from $i$ to $j$ in $G$. Note that a matching is a set of pairwise non-adjacent edges. Thus, each edge in the matching connects two vertices, and no vertex is part of two matching (a matched vertex is matched with exactly one other vertex). A perfect matching is a matching where each vertex has been matched. Now, for each matching edge obtained, you can consider the two end vertices to be paired up. The constraint of "minimum-weight" when obtaining the matching ensures that the total weight of each edge in the matching is as small as possible. Since the weight of each edge is the distance between its end points in $G$, which in turn is the number of edges that need to be duplicated when the end points are paired up - this condition ensures that globally, the total number of edge duplication is minimized. Obtaining such a matching is described in [2], and is based on the Blossom algorithm. An efficient implementation is described by Kolmogorov [3] (preprint copy) with an implementation here. The implementation is an improvement over the ideas and review presented by Cook and Rohe in [4]. This can be done $O(n^3)$.
3. Once the matching is obtained, each odd vertex is paired with another odd vertex. This is the pairing that you want.

Thus, you can obtain the optimal "Eulerization" in time polynomial (cubic) in the number of odd-vertices. This is based on a paper by Edmonds and Johnson [2] which solves the Chinese postman problem.

References:

1. Steven S. Skiena. The Algorithm Design Manual. ISBN: 978-1-84800-069-8 e-ISBN: 978-1-84800-070-4 and DOI: 10.1007/978-1-84800-070-4
2. J. Edmonds and E. Johnson. Matching, Euler tours, and the Chinese postman. Mathematical Programming, 5:88–124, 1973.
3. Vladimir Kolmogorov. Blossom V: A new implementation of a minimum cost perfect matching algorithm. In Mathematical Programming Computation (MPC), July 2009, 1(1):43-67.
4. W. Cook and A. Rohe. Computing minimum-weight perfect matchings. INFORMS Journal on Computing, 11(2):138–148, February 1999.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9126