Tutte Colloquium - Laura Sanita

Title: On the hardness of computing the diameter of a polytope

Abstract:

The diameter of a polytope P is given by the maximum length of a shortest path between a pair of vertices on P. Giving bounds on the diameter of a polytope is a fundamental research topic in theoretical computer science and discrete mathematics, motivated by the (still unknown) existence of a polynomial pivot rule for the Simplex Algorithm for solving Linear Programs.

The diameter of a polytope has been studied from many different perspectives, including a computational complexity point of view. In particular, Frieze and Teng in 1994 showed that computing the diameter of a polytope is weakly NP-hard.
In this talk, we will strengthen this hardness result, by exploiting the structure of a notorious and well-studied polytope in the optimization community: the fractional matching polytope. In particular, we will give an exact characterization of the diameter of this polytope, and then use it to derive strong NP-hardness (in fact, APX-hardness) for the problem of computing the diameter.