  In the Mixed Chinese Postman Problem (MCPP), given a weighted mixed graph $G$
($G$ may have both edges and arcs), our aim is to find a minimum weight closed
walk 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 fixed-parameter
tractable as proved by van Bevern {\em et al.} (in press) and Gutin, Jones and
Sheng (ESA 2014), respectively. In this paper, we consider the unweighted
version of MCPP. Solving an open question of van Bevern {\em et al.} (in
press), we show that somewhat unexpectedly MCPP parameterized by the
(undirected) treewidth of $G$ is W[1]-hard. In fact, we prove that even the
MCPP parameterized by the pathwidth of $G$ is W[1]-hard. On the positive side,
we show that the unweighted version of MCPP parameterized by tree-depth is
fixed-parameter tractable. We are unaware of any natural graph parameters
between pathwidth and tree-depth and so our results provide a dichotomy of the
complexity of MCPP. Furthermore, we believe that MCPP is the first problem
known to be W[1]-hard with respect to treewidth but FPT with respect to
tree-depth.
