Series–parallel graphs are windy postman perfect Original Research Article

The windy postman problem is the NP-hard problem of finding the minimum cost of a tour traversing all edges of an undirected graph, where the cost of an edge depends on the direction of traversal. Given an undirected graph G, we consider the polyhedron image induced by a linear programming relaxation of the windy postman problem. We say that G is windy postman perfect if image is integral. There exists a polynomial-time algorithm, based on the ellipsoid method, to solve the windy postman problem for the class of windy postman perfect graphs. By considering a family of polyhedra related to image, we prove that series–parallel graphs are windy postman perfect, therefore solving a conjecture of Win.