Lehrstuhl Mathematik & InformatikOn Relations between Graph Problems, Mathematical Programming and the Geometry of Numbers
Abstract. We are interested in relating computationally hard graph problems to classical and well-studied problems in the geometry of numbers, As a first step in this direction, we associate an ellipsoid EG and a lattice LG with any undirected finite graph G. It is shown that the NP-complete problem of finding a maximum cut in G is equivalent to finding the smallest dilatation of EG which leads to a nonempty intersection with Zn. Maximum cuts in G are similarly related to shortest vectors in LG which have nonzero coordinates with respect to a given basis. These descriptions of maximum cuts in geometric terms imply the NP-completeness of a collection of quite basic problems in the geometry of numbers. The implications on 'Integer Convex Quadratic Programming' are also investigated.