- INSTANCE:
Mixed graph
,
length
for each
such
that for every arc there is a parallel edge of no greater length.
- SOLUTION:
A cycle in
*G*(possibly containing repeated vertices) that includes each directed edge in*A*at least once, traversing such edges only in the specified direction. - MEASURE:
The total length of the cycle.

*Good News:*Approximable within 9/5 [171].*Garey and Johnson:*ND26