Wednesday, 15:45 - 16:10 h, Room: H 3013


Aleksandr Maksimenko
The common face of some 0/1 polytopes with NP-complete nonadjacency relations


We consider so-called double covering polytopes (DCP).
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 graph polytopes, 3-SAT polytopes, partial order polytopes, traveling salesman polytopes, and some others.
Thus, these families of polytopes inherit the property of NP-completness of nonadjacency relations from DCP.
We show also that the graph of a double covering polytope has superpolynomial clique number.
The same is true for the mentioned families of polytopes.


Talk 2 of the contributed session Wed.3.H 3013
"Polyhedra in combinatorial optimization" [...]
Cluster 2
"Combinatorial optimization" [...]


  To apply for USA Payday Loans you don't have to seek the help of relatives or go to a bank. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis Sale was obtained in Europe, Australia, New Zealand.