Advertisement
Published in:
2015 | OriginalPaper | Chapter
Structural Parameterizations of the Mixed Chinese Postman Problem
Authors : Gregory Gutin, Mark Jones, Magnus Wahlström
Published in: Algorithms - ESA 2015
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In the Mixed Chinese Postman Problem (MCPP), given a 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 in
G
or the number of arcs in
G
is fixed-parameter tractable as proved by van Bevern
et al.
(2014) and Gutin, Jones and Sheng (2014), respectively. In this paper, we consider the unweighted version of MCPP. 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 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. We are unaware of any natural graph parameters between pathwidth and treedepth and so our results provide a dichotomy of the complexity of MCPP.