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