  In 1995 T. Matsui considered a special family 0/1-polytopes for which the
problem of recognizing the non-adjacency of two arbitrary vertices is
NP-complete. In 2012 the author of this paper established that all the
polytopes of this family are present as faces in the polytopes associated with
the following NP-complete problems: the traveling salesman problem, the
3-satisfiability problem, the knapsack problem, the set covering problem, the
partial ordering problem, the cube subgraph problem, and some others. In
particular, it follows that for these families the non-adjacency relation is
also NP-complete. On the other hand, it is known that the vertex adjacency
criterion is polynomial for polytopes of the following NP-complete problems:
the maximum independent set problem, the set packing and the set partitioning
problem, the three-index assignment problem. It is shown that none of the
polytopes of the above-mentioned special family (with the exception of a
one-dimensional segment) can be the face of polytopes associated with the
problems of the maximum independent set, of a set packing and partitioning, and
of 3-assignments.
