backup forward

Go backward to 22 Polytope Isomorphism
Go up to 4 Isomorphism
Go forward to 24 Selfduality of Polytopes
XHTML 1.0

23 Isomorphism of Vertex-Facet Incidences

Input: Vertex-facet incidence matrices AP and AQ of polytopes P and Q, respectively
Output: "Yes" if AP can be transformed into AQ by row and column permutations, "No" otherwise
Status (general): Graph isomorphism complete
Status (fixed dim.): Polynomial time
The problem remains graph isomorphism complete even if V- and H-descriptions of P and Q are part of the input data [34].

In constant dimension the problem can be solved in polynomial time by a reduction [34] to the graph isomorphism problem for graphs of bounded degree, for which a polynomial time algorithm is known (Luks [41]).

Problem 22 can polynomially be reduced to this problem. For polytopes of bounded dimension both problems are polynomial time equivalent.


backup forward Why are some symbols not displayed correctly?