The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth

In the Mixed Chinese Postman Problem (MCPP), given a weighted mixed graph G
(it may have both edges and arcs), our aim is to nd a closed walk of minimum weight traversing each edge and arc at least once. The MCPP parameterized by the number of edges in G or the number of arcs in G is xed-parameter tractable as proved by van Bevern et al. (2014) and Gutin, Jones and Sheng (2014), respectively. Solving an open question of van Bevern et al. (2014), we show that somewhat unexpectedly MCPP parameterized by the (undirected) treewidth of G is W[1]-hard. In fact, we prove that even the unweighted MCPP parameterized by the pathwidth of G is W[1]-hard. On the positive side, we show that MCPP parameterized by treedepth is fixed-parameter tractable (even with arbitrary
integer weights). We are unaware of any widely studied graph parameters between path-width and treedepth and so our results provide a close characterization of the complexity of MCPP.