## Samenvatting

The (combinatorial) diameter of a polytope P ⊆ 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 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 exact characterization of the diameter of the fractional matching polytope, that is of independent interest.

Originele taal-2 | Engels |
---|---|

Titel | Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 |

Redacteuren | Mikkel Thorup |

Uitgeverij | IEEE Computer Society |

Pagina's | 910-921 |

Aantal pagina's | 12 |

ISBN van elektronische versie | 9781538642306 |

DOI's | |

Status | Gepubliceerd - 30 nov. 2018 |

Extern gepubliceerd | Ja |

Evenement | 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 - Paris, Frankrijk Duur: 7 okt. 2018 → 9 okt. 2018 |

### Congres

Congres | 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 |
---|---|

Land/Regio | Frankrijk |

Stad | Paris |

Periode | 7/10/18 → 9/10/18 |