Input: | Vertex-facet incidence matrices A and _{P}A of
polytopes _{Q}P and Q, respectively |
---|---|

Output: | "Yes" if A can be transformed into _{P}A by row and
column permutations, "No" otherwise_{Q} |

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

Related problems: | 22, 21 |
---|