Efficient Algorithms for Eulerian Extension and Rural Postman

The aim of directed Eulerian extension problems is to make a given directed, possibly arc-weighted, (multi-)graph Eulerian by adding a minimum-cost set of arcs. These problems have natural applications in scheduling and arc routing and are closely related to the Chinese Postman and Rural Postman problems. Our main result is to show that the NP-hard Weighted Multigraph Eulerian Extension problem is fixed-parameter tractable with respect to the number ${k}$ of extension arcs. For a directed $n$-vertex multigraph, the corresponding running time amounts to ${\ensuremath{O(4^{k}\cdot n^3)}}$. This also implies a fixed-parameter tractability result for the “equivalent” Rural Postman problem parameterized above guarantee. In addition, we present several polynomial-time algorithms for natural Eulerian extension problems, including undirected variants which can be defined analogously to the directed ones.

© 2013, Society for Industrial and Applied Mathematics