On the complexity of checking self-duality of polytopes and its relations to vertex enumeration and graph isomorphism

Hans Raj Tiwary, Khaled Elbassioni

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

We study the complexity of determining whether a polytope given by its vertices or facets is combinatorially isomorphic to its polar dual. We prove that this problem is Graph Isomorphism hard, and that it is Graph Isomorphism complete if and only if Vertex Enumeration is Graph Isomorphism easy. To the best of our knowledge, this is the first problem that is not equivalent to Vertex Enumeration and whose complexity status has a non-trivial impact on the complex-it}^ of Vertex Enumeration irrespective of whether checking Self-duality turns out to be strictly harder than Graph Isomorphism or equivalent to Graph Isomorphism. The constructions employed in the proof yield a class of self-dual polytopes that are interesting on their own. In particular, this class of self-dual polytopes has the property that the facet-vertex incident matrix of the polytope is transposable if and only if the matrix is symmetrizable as well. As a consequence of this construction, we also prove that checking self-duality of a polytope, given by its facet-vertex incidence matrix, is Graph Isomorphism complete, thereby answering a question of Kaibel and Schwartz.

Original languageBritish English
Title of host publicationProceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08
Pages192-198
Number of pages7
DOIs
StatePublished - 2008
Event24th Annual Symposium on Computational Geometry, SCG'08 - College Park, MD, United States
Duration: 9 Jun 200811 Jun 2008

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Conference

Conference24th Annual Symposium on Computational Geometry, SCG'08
Country/TerritoryUnited States
CityCollege Park, MD
Period9/06/0811/06/08

Keywords

  • Computational geometry
  • Graph isomorphism
  • Isomorphism
  • Polytopes
  • Self-duality
  • Vertex enumeration

Fingerprint

Dive into the research topics of 'On the complexity of checking self-duality of polytopes and its relations to vertex enumeration and graph isomorphism'. Together they form a unique fingerprint.

Cite this