Can I read Parameterized Complexity of the $k$-Arc Chinese Postman Problem on EtoBox?

Parameterized Complexity of the $k$-Arc Chinese Postman Problem by Gutin, Gregory; Jones, Mark; Sheng, Bin is a scholarly article available to read on EtoBox.

What is Parameterized Complexity of the $k$-Arc Chinese Postman Problem about?

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.

Author

Gutin, Gregory; Jones, Mark; Sheng, Bin

Published

2014

Language

EN