Parameterized complexity of the k-arc Chinese Postman Problem. / Gutin, Gregory; Jones, Mark; Sheng, Bin.

In: Journal of Computer and System Sciences, Vol. 84, 03.2017, p. 107–119.

Research output: Contribution to journalArticle

Published

Documents

Links

Abstract

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
Volume84
Early online date9 Sep 2016
DOIs
Publication statusPublished - Mar 2017
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 26782495