Complexity of the Mixed Postman Problem with Restrictions on the Edges
Francisco Javier Zaragoza Martínez · 2006
The mixed postman problem consists of finding a minimum cost tour of a connected mixed graph traversing all its vertices, edges, and arcs at least once. We consider the variant of the mixed postman problem where all edges must be traversed exactly once. We prove that the feasibility version of this problem is NP-complete. We introduce a necessary condition for feasibility and show that it can be tested in polynomial time. We prove that this condition is also sufficient if the directed components of the mixed graph form a directed walk. Finally, we give a linear programming formulation to solve the minimization version of this problem if the directed components of the mixed graph form a forest.