Self-Duality of Polytopes and its Relations to Vertex Enumeration and Graph Isomorphism

Hans Raj Tiwary, Khaled Elbassioni

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


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 complexity 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
Pages (from-to)729-742
Number of pages14
JournalGraphs and Combinatorics
Issue number3
StatePublished - May 2014


  • Graph isomorphism
  • Polytopes
  • Self-duality
  • Vertex enumeration


Dive into the research topics of 'Self-Duality of Polytopes and its Relations to Vertex Enumeration and Graph Isomorphism'. Together they form a unique fingerprint.

Cite this