This article is cited in 8 papers

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

A. N. Maksimenko

P. G. Demidov Yaroslavl State University, Yaroslavl, Russia

Abstract: 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.

UDC: 519.854.2+519.161

 English version: Journal of Mathematical Sciences (New York), 2014, 203:6, 823–832

Bibliographic databases:

• 
•