- INSTANCE:
Graph
,
length
for each ,
subset
,
subset .
- SOLUTION:
A cycle in
*G*that visits each vertex in*V'*exactly once and traverses each edge in*E'*. - MEASURE:
The total length of the cycle.

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