  The (combinatorial) diameter of a polytope $P \subseteq \mathbb R^d$ is the
maximum value of a shortest path between a pair of vertices on the 1-skeleton
of $P$, that is the graph where the nodes are given by the $0$-dimensional
faces of $P$, and the edges are given the 1-dimensional faces of $P$. The
diameter of a polytope has been studied from many different perspectives,
including a computational complexity point of view. In particular, [Frieze and
Teng, 1994] showed that computing the diameter of a polytope is (weakly)
NP-hard.
  In this paper, we show that the problem of computing the diameter is strongly
NP-hard even for a polytope with a very simple structure: namely, the
\emph{fractional matching} polytope. We also show that computing a pair of
vertices at maximum shortest path distance on the 1-skeleton of this polytope
is an APX-hard problem. We prove these results by giving an \emph{exact
characterization} of the diameter of the fractional matching polytope, that is
of independent interest.

Combinatorics;Optimization and Control