The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth. / Gutin, Gregory; Jones, Mark; Wahlstrom, Magnus.

In: SIAM Journal on Discrete Mathematics, Vol. 30, No. 4, 2016, p. 2177-2205.

Research output: Contribution to journalArticle

Published

Documents

Abstract

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
Volume30
Issue number4
Early online date29 Nov 2016
DOIs
Publication statusPublished - 2016
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 26909097