NP-Completeness of Non-Adjacency Relations on Some 0-1 Poly topes

摘要

In this paper, we discuss the adjacency structures of some classes of 0-1 polytopes including knapsack polytopes, set covering poly-topes 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.