Arc-routing for winter road maintenance

The arc-routing problems are known to be notoriously hard. We study here a natural arc-routing problem on trees and more generally on bounded tree-width graphs and surprisingly show that it can be solved in a polynomial time. This implies a sub-exponential algorithm for the planar graphs and small number of maintaining cars, which is of practical relevance.