@inproceedings{b27bd1f700004dc3842c18a57e26a3bf,

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

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.",

keywords = "Computational geometry, Graph isomorphism, Isomorphism, Polytopes, Self-duality, Vertex enumeration",

author = "Tiwary, {Hans Raj} and Khaled Elbassioni",

year = "2008",

doi = "10.1145/1377676.1377707",

language = "British English",

isbn = "9781605580715",

series = "Proceedings of the Annual Symposium on Computational Geometry",

pages = "192--198",

booktitle = "Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08",

note = "24th Annual Symposium on Computational Geometry, SCG'08 ; Conference date: 09-06-2008 Through 11-06-2008",

}