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

REFERENCES

• 1: Dan Archdeacon , Seiya Negami, The construction of self-dual projective polyhedra, Journal of Combinatorial Theory Series B, v.59 n.1, p.122-131, Sept. 1993 [doi>10.1006/jctb.1993.1059]
• 2: David Avis , David Bremner , Raimund Seidel, How good are convex hull algorithms?, Computational Geometry: Theory and Applications, v.7 n.5-6, p.265-301, April 1997 [doi>10.1016/S0925-7721(96)00023-5]
• 3: E. Boros, V. Gurvich, and I. Zverovich. Neighborhood hypergraphs of bipartite graphs. Technical report, Rutgers Center for Operations Research, 2006.
• 4: D. Bremner, K. Fukuda, and A. Marzetta. Primal - dual methods for vertex and facet enumeration. Discrete & Computational Geometry, 20(3):333--357, 1998.
• 5: J. Erickson. Faces of intricate polytopes. Web Notes: http://compgeom.cs.uiuc.edu/~jeffe/open/intricate.html, 2000.
• 6: R. M. Freund and J. B. Orlin. On the complexity of four polyhedral set containment problems. Mathematical Programming, 33(2):139--145, 1985.
• 7: B. Grünbaum. Convex Polytopes Second Edition prepared by V. Kaibel, V. L. Klee and G. M. Ziegler, volume 221 of Graduate Texts in Mathematics. Springer, 2003.
• 8: B. Grünbaum and G. C. Shephard. Is self-duality involutory? American Mathematical Monthly, 95:729--733, 1988.
• 9: S. Jendroľ, A non-involutory selfduality, Discrete Mathematics, v.74 n.3, p.325-326, April 1989 [doi>10.1016/0012-365X(89)90144-1]
• 10: Volker Kaibel , Marc E. Pfetsch, Computing the face lattice of a polytope from its vertex-facet incidences, Computational Geometry: Theory and Applications, v.23 n.3, p.281-290, November 2002 [doi>10.1016/S0925-7721(02)00103-7]
• 11: V. Kaibel and A. Schwartz. On the complexity of polytope isomorphism problems. Graphs and Combinatorics, 19(2):215--230, 2003.
• 12: Leonid Khachiyan , Endre Boros , Konrad Borys , Khaled Elbassioni , Vladimir Gurvich, Generating all vertices of a polyhedron is hard, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.758-765, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109640]
• 13: P. McMullen. The maximum numbers of faces of a convex polytope. Mathematica, 17:179--184, 1970.
• 14: Peter Bro Miltersen , N. V. Vinodchandran, Derandomizing Arthur-Merlin Games Using Hitting Sets, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.71, October 17-18, 1999
• 15: Hans Raj Tiwary, On the hardness of minkowski addition and related operations, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea [doi>10.1145/1247069.1247124]
• 16: G. M. Ziegler. Lectures on Polytopes, volume 152 of Graduate Texts in Mathematics. Springer-Verlag.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
computational geometry, graph isomorphism, isomorphism, polytopes, self-duality, vertex enumeration