- INSTANCE:
Graph
.
- SOLUTION:
A decomposition of the graph into two factors,
and ,
with
equal diameters.
- MEASURE:
The diameter of .

*Bad News:*Not approximable within 3/2 for any [406].*Comment:*Variation in which the diameters of and do not need to be equal, and where the objective is to minimize the sum of the diameters, is not approximable within 5/4 [406].