I am working on programming a function for Mixed Chinese Postman problems or MCP in arc routing. The input is a mixed graph with edges and arcs that have weights associated with them. The output is a walk that traverses each edge at least once with a minimal cost. I am wondering how to implement an efficient algorithm for an extension of the FindPostmanTour for mixed graphs. The MCPP is NP hard. The best heuristic, which approaches the best solution but cannot be guaranteed to be the optimal solution and is usually around 0.5% to a few percent away from the optimum is 3/2 times the optimum. I have an algorithm named MIXED1.

1. Evendegree: Let G={V,E,A} be a strongly connected mixed graph. Ignoring arc directions, solve a minimum-cost matching of odd-degree vertices and augment G by adding all links used for the matching solutino. The resulting graph G'={V',E',A'} is an even graph.
2. Inoutdegree: With supplies and demands computed in graph {V,A'} solve a minimum cost flow problem in G' to obtain a symmetric graph G''={V,E'',A} the author Frederickson points out that after this step some vertices in G'' may have odd degree.
3. Evenparity: Let VO bet the set of odd-degree nodes in G''. Identify cycles consisting of alternating paths in A''\A and E'' with each path starting and ending at vertices in VO. The paths in A''\A will be formed without considering the arc directions. As the cycles are covered, their arcs will be either duplicated or deleted and their edges directed, so the resulting graph becomes even, while maintaining the symmetry for each vertex.

I am working on the code for evendegree. I can check if the graph is connected with ConnectedGraphQ. I can transform the graph into an undirected graph with UndirectedGraph. I can select the odd-degree vertices with

Select[VertexList[G],OddQ[VertexDegree[G,#]]&]

I am wondering how to compute a minimum-cost matching on these odd-degree vertices. I think I should FindIndependentEdgeSet but I'm not sure.