| Input: | Polytope P in H-description |
|---|---|
| Output: | The diameter of P |
| Status (general): | NP-hard |
|---|---|
| Status (fixed dim.): | Polynomial time |
|
Frieze and Teng [21] gave the proof of NP-hardness. For
fixed dimension, one can enumerate all vertices
(Problem 1), construct the graph and
then compute the diameter in polynomial time.
The complexity status is unknown for simple polytopes. For simplicial polytopes the problem can be solved in polynomial time: Since simplicial polytopes have at most as many vertices as facets, one can enumerate their vertices (see Problem 1), and finally compute the graph (and hence the diameter) from the vertex-facet incidences in polynomial time. If P is given in V-description, one can compute the graph (1-skeleton, see Problem 5) and hence the diameter in polynomial time. |