Relaxations for some NP-hard problems based on exact subgraphs

The classification of combinatorial optimization problems into tractable and NP-hard problems raises the question of how to deal with the latter class. It is commonly believed that NP-hard problems are intractable, but there is no rigorous proof for this. In fact, this is one of the famous open problems in the Clay millenium collection of unsolved mathematical problems. After the introduction of computational complexity in the early 1970`s big scientific efforts were put into the study of NP-hard problems. Complexity theory is concerned with the worst case behaviour of algorithms for particular problem classes. But even if a problem is considered intractable, it is still a mathematical challenge to get tight approximations using practically efficient methods. It is the purpose of this project to develop and extend the computational machinery to deal with several prominent NP-hard graph optimization problems. Specifically we investigate semidefinite optimization techniques to study Max-Cut, Stable-Set and Vertex- Coloring in graphs. The innovative aspect of the project lies in the way that we propose to get increasingly tight approximations. Our idea is to inforce the condition that the projection of a solution to (all) k-node subsets is exact, i.e. in the convex hull of feasible solutions. The cardinality k is selected to be small enough, so that the projections can be handled efficiently. The challenges consist in developing tools to identify a selection of subsets on which to project, the separation problem. We will use problem specific techniques and also separations based on copositive matrices. Moreover it is necessary to investigate which algorithmic approaches yield the highest computational efficiency. We propose to investigate the use of the partial Lagrangian dual which allows us to combine bundle methods with simple oracles based on semidefinite programming. Finally, as a long term goal, it is planned to integrate the new techniques into existing software packages to solve problems to optimality by Branch and Bound.

Combinatorial optimization problems can be viewed as decision problems in the sense of theoretical computer science: Does there exist a feasible solution with value less than or equal to z, or do all solutions have a value greater than z? These decison problems fall into two groups. The first group contains those problems where 'YES'-instances can be recognized in polynomial time. The second group consists of the remaining problems. In the 'P-versus-NP' conjecture it is conjectured that problems in the second class may require in the worst case an exponential effort to reach an optimal solution. The project is devoted to the bandwidth problem, which belongs to the second class of problems. Given a symmetric 0-1 matrix A and a number k, the decision problem consists in deciding whether a simultaneous permutation of the rows and columns of A exists, such that all nonzeros of the permuted matrix have distance at most k from the main diagonal of the matrix, or whether any permuted matrix has at least one nonzero of distance greater than k from the main diagonal. This problem is extremely difficult to solve exactly, even for very simple graphs such as trees with maximum vertex degree equal three. This problem has a natural reformulation as a combinatorial optimization problem in 0-1 variables. We interpret the matrix A as the adjacency matrix of a graph. To get a handle on the problem we consider vertex partitions of the graph, and consided only edges which join different partition blocks. We now look for partitions where the number of edges joining blocks far away is minimized. This leads to a quadratic minimization problem in 0-1 variables, which is still in the second class of difficult problems. This graph partition problem can be approximated using linear optimization with positive semidefinite matrices. The main focus of the project lies in the algorithmic treatment of this semidefinite optimization problem. The identification of cutting planes which are derived from a polyhedral description of the convex hull of feasible solutions plays a key role to get tight approximations to the partition problem, It turns out that the 'method of alternating directions' leads to good approximations even for larger instances. It lead to new and tighter bounds for the bandwidth for a number of graphs. An interesting class of graphs are two-dimensional lattice graphs. Here we were able to determine the bandwidth exactly for smaller instances, and obtained tight estimates in general. Finally we applied this approach also to graphs from the literature, and we could substantially improve previous estimates on their bandwidth.