ND38 M INIMUM G ENERAL R OUTING

     
• I NSTANCE : Graph , length for each , subset , subset .
• S OLUTION : A cycle in G that visits each vertex in V' exactly once and traverses each edge in E' .
• M EASURE : The total length of the cycle.

• Good News: Approximable within 3/2 [ 188 ].
• Comment: The special case where V'=V is called the rural postman problem.    
• Garey and Johnson: Generalization of ND27