S
OLUTION
:
A decomposition of the graph into two factors,
and
, with
equal diameters.
M
EASURE
:
The diameter om
.
Bad News:
Not approximable within 3/2
for any
[
297
].
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
[
297
].