Norsk English

# Efficient Algorithms for Eulerian Extension and Rural Postman

## Abstract

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

English

### Author(s)

• Frederic Dorn
• Hannes Moser
• Rolf Niedermeier
• Mathias Weller

### Affiliation

• SINTEF Energy Research / Energisystemer
• Friedrich Schiller University of Jena
• Technical University Berlin

2013

### Published in

SIAM Journal on Discrete Mathematics

0895-4801

### Publisher

Society for Industrial and Applied Mathematics

27

1

75 - 94

### DOI

https://doi.org/10.1137/110834810