MINIMUM CHINESE POSTMAN FOR MIXED GRAPHS

• INSTANCE: Mixed graph $G=\left(V,A,E\right)$, length $l(e)\in N$ for each $e\in A\cup E$.

• SOLUTION: A cycle in G (possibly containing repeated vertices) that includes each directed and undirected edge at least once, traversing directed edges only in the specified direction.

• MEASURE: The total length of the cycle.

  
  

• Good News: Approximable within 3/2 [413].

• Garey and Johnson: ND25