FUNDAMENTALNAYA
I PRIKLADNAYA MATEMATIKA

(FUNDAMENTAL AND APPLIED MATHEMATICS)

2013, VOLUME 18, NUMBER 2, PAGES 105-118

**The common face of some $0/1$-polytopes with
NP-complete nonadjacency relation**

A. N. Maksimenko

Abstract

View as HTML
View as gif image

In this paper, we consider so-called double covering polytopes.
In 1995, Matsui showed that the problem of checking nonadjacency on
these polytopes is NP-complete.
We show that double covering polytopes are faces of the following
polytopes: knapsack polytopes, set covering polytopes, cubic subgraph
polytopes, $3$-SAT polytopes, partial
order polytopes, traveling salesman polytopes, and some others.

Location: http://mech.math.msu.su/~fpm/eng/k13/k132/k13208h.htm

Last modified: January 7, 2014