Affine maps between quadratic assignment polytopes and subgraph isomorphism polytopes

Abstract: We consider two polytopes. The quadratic assignment polytope

Q A P (n)

is the convex hull of the set of tensors

x o t i m e s x

,

x i n P_{n}

, where

P_{n}

is the set of

n i m e s n

permutation matrices. The second polytope is defined as follows. For every permutation of vertices of the complete graph

K_{n}

we consider appropriate

permutation matrix of the edges of

K_{n}

. The Young polytope

P ((n - 2, 2))

is the convex hull of all such matrices. In 2009, S. Onn showed that the subgraph isomorphism problem can be reduced to optimization both over

Q A P (n)

and over

P ((n - 2, 2))

. He also posed the question whether

Q A P (n)

and

P ((n - 2, 2))

, having

n!

vertices each, are isomorphic. We show that

Q A P (n)

and

P ((n - 2, 2))

are not isomorphic. Also, we show that

Q A P (n)

is a face of

P ((2 n - 2, 2))

, but

P ((n - 2, 2))

is a projection of

Q A P (n)

.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Affine maps between quadratic assignment polytopes and subgraph isomorphism polytopes