NP-Completeness of Non-Adjacency Relations on Some 0-1 Polytopes

: In this paper, we discuss the adjacency structures of some classes of 0-1 polytopes including knapsack polytopes, set covering polytopes and 0-1 polytopes represented by complete sets of implicants. We show that for each class of 0-1 polytope, non-adjacency test problems are NP-complete. For equality constrained knapsack polytopes, we can solve adjacency test problems in pseudo polynomial time. 1 Introduction It seems that an adjacency criterion for a class of polyhedra could provide a basis of an efficient algorithm which uses some sorts of local search technique. For this purpose, it is necessary to have an efficient algorithm for checking adjacency. In [16], Papadimitriou showed that the problem of checking non-adjacency on the travelling salesman polytope is NP-complete. So, one cannot expect an efficient edge-following type algorithm for the travelling salesman problem. However, there exist some classes of combinatorial polytopes, including matching polytopes [4, 6], vertex pac...