摘要 In the Mixed Chinese Postman Problem (MCPP), given
an edge-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
was known to be fixed-parameter tractable using a simple argument.
Solving an open question of van Bevern et al., we prove that the MCPP
parameterized by the number of arcs is also fixed-parameter tractable.
Our proof is more involved and, in particular, uses a very useful result
of Marx, O’Sullivan and Razgon (2013) on the treewidth of torso graphs
with respect to small separators.