- INSTANCE:
Multigraph
,
initial vertex ,
length
for each .
- SOLUTION:
A collection of
*k*cycles, each containing the initial vertex*s*, that collectively traverse every edge in the graph at least once. - MEASURE:
The maximum length of the
*k*cycles.

*Good News:*Approximable within*2-1/k*[171].