  The Hierarchical Chinese Postman Problem is finding a shortest traversal of
all edges of a graph respecting precedence constraints given by a partial order
on classes of edges. We show that the special case with connected classes is
NP-hard even on orders decomposable into a chain and an incomparable class. For
the case with linearly ordered (possibly disconnected) classes, we get
5/3-approximations and fixed-parameter algorithms by transferring results from
the Rural Postman Problem.
