  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.
