On the complexity of edge traversing
Christos H. Papadimitriou · Journal of the ACM · 1976
It is shown that the Chinese Postman Problem, although tractable in the totally directed and the totally undirected cases, is NP-complete in the mixed case. A simpler version of the same problem is shown algorithmically equivalent to the max-flow problem with unit edge capacities.