The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth

Research output: Contribution to journalArticlepeer-review

200 Downloads (Pure)


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.
Original languageEnglish
Pages (from-to)2177-2205
Number of pages29
JournalSIAM Journal on Discrete Mathematics
Issue number4
Early online date29 Nov 2016
Publication statusE-pub ahead of print - 29 Nov 2016

Cite this