Complexity of a restricted chinese postman problem

The Chinese Postman Problem (CPP) on mixed graphs is shown to be NP-complete. It remains NP-complete even if restricted to those whose edges all have equal length, or to one on mixed planner graphs, or to one on mixed graphs with nodes of degree three. CPP can be solved in polynomial time if the graph is either directed or undirected. In this paper, the authors show that even if the number of traverses for each edge is restricted to at most twice, CPP on the mixed graphs (called 2-CPP) is NP-complete, and if the number of traverses for each edge is restricted to exactly once, CPP on the mixed graphs (called 1-CPP) is in P. They also show complexity of two related functions: (i) in 2-CPP the function that calculates the number of delivery paths is #P-complete, on the other hand, (ii) in CPP the function that calculates the minimum of the maximum traverse numbers for each delivery path of cost k or less belongs to the class in the polynomial time hierarchy. [In Japanese.]