Two graph isomorphism polytopes

Details Two graph isomorphism polytopes Two graph isomorphism polytopes

2008-01-09

arxiv.org/abs/0801.1410v2

Discrete Mathematics, 309:2934--2936, 2009

Computer Science

Computational Complexity

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Two graph isomorphism polytopes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Two graph isomorphism polytopes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two graph isomorphism polytopes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-670074