Two graph isomorphism polytopes

Abstract

The convex hull ${\psi }_{n,n}$ of certain $(n!{)}^2$ tensors was considered recently in connection with graph isomorphism. We consider the convex hull ${\psi }_n$ of the $n!$ diagonals among these tensors. We show: 1. The polytope ${\psi }_n$ is a face of ${\psi }_{n,n}$. 2. Deciding if a graph $G$ has a subgraph isomorphic to $H$ reduces to optimization over ${\psi }_n$. 3. Optimization over ${\psi }_n$ reduces to optimization over ${\psi }_{n,n}$. In particular, this implies that the subgraph isomorphism problem reduces to optimization over ${\psi }_{n,n}$.

References in corpus (1)

• On the graph isomorphism problem

Cited by in corpus (1)

• A Family of Counter Examples to an Approach to Graph Isomorphism