Complexity of the Mixed Postman Problem with Restrictions on the Arcs
Zaragoza Martinez, Francisco Javier · 2006
The mixed postman problem consists of finding a minimum cost tour of a mixed graph traversing all its vertices, edges, and arcs at least once. We consider the variant of the mixed postman problem where all arcs must be traversed exactly once. We prove that the decision version of this problem is NP-complete. We give an integer programming formulation of this problem and we prove that one of its linear relaxations defines an integral polyhedron and can be solved in polynomial time