AProPo -- 23 Isomorphism of Vertex-Facet Incidences

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

23 Isomorphism of Vertex-Facet Incidences

Input:	Vertex-facet incidence matrices A_P and A_Q of polytopes P and Q, respectively
Output:	"Yes" if A_P can be transformed into A_Q 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.