The Windy Postman Problem seeks the cheapest tour in a complete undirected graph, that traverses each edge at least once; the cost of traversing an edge is positive and may depend on the direction, in which an edge is traversed.
It can be assumed that the graph is complete.
Zaw Win has proved that the problem is solvable in polynomial time if the graph is eulerian and NP-hard otherwise.
Now, as the graph is complete, it is eulerian, iff the number of vertices is odd and a complete non-eulerian graph can be rendered eulerian by removing the edges of a perfect matching, which leads to the following
- in an optimal solution to a non-eulerian Windy Postman Problem of a complete graph the set of edges that are traversed more than once constitute to a perfect matching and each of those edges is traversed exactly twice?
- what is the performance of the heuristic of taking as the edges of the perfect matching the ones whose weight-sum over both directions of traversal is minimal and then adding the edges of the shortest euler tour through the other edges?
- Is the minimum weight matching the best choice of edges to traverse twice?
the rationale behind the heuristic is that the postman would move along the euler tour and whenever a vertex is encountered that is adjacent to matching edge that hasn't been traversed yet, traverse it and return along it again, essentially treating the matching edges as deadend streets.
As both parts of the heuristic, determining an optimal general perfect matching and determining the optimal solution to the restriction of the Windy Postman Problem to an eulerian spanner, are polynomial and so is the suggested heuristic.
if all directional edgeweights in a non-eulerian Windy Postman Problem are strictly positive, then the multiset of edges resembling the optimal eulerian tour that visits each edge at least once, must be of minimal cardinality because otherwise the length of the tour could be reduced by removing a two-regular directed subgraph of positive weightsum while preserving the existence of an eulerian tour.
The smallest possible cardinality of an eulerian tour through the graph of the problem instance is however achieved by bidirectional traversal of the edges of a perfect matching of the odd-degree vertices of the undirected graph.
Therefore the "structure" of the optimal solution must be the same as the one suggested for the heuristic.
Thus the heuristic is a relaxed version of a correct algorithm, the relaxation being the not necessarily optimal choice of the minimum weight matching as the edges that shall be traversed bidirectionally on an eulerian tour.