Parameterized complexity of the k-arc Chinese Postman Problem

Gregory Gutin, Mark Jones, Bin Sheng

Research output: Contribution to journalArticlepeer-review

50 Downloads (Pure)


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 well-known result of Marx, O'Sullivan and Razgon (2013) on the treewidth of torso graphs with respect to small separators. We obtain a small cut analog of this result, and use it to construct a tree decomposition which, despite not having bounded width, has other properties allowing us to design a fixed-parameter algorithm.
Original languageEnglish
Pages (from-to)107–119
Number of pages13
JournalJournal of Computer and System Sciences
Early online date9 Sept 2016
Publication statusPublished - Mar 2017

Cite this