Giovanni Rinaldi (IASI)


Maximum weight cuts in graphs and extensions


Max-Cut, i.e., the problem of finding a cut of maximum weight in a weighted graph, is one on the most studied and best known hard optimization problems on graphs. Because on its great interest among the optimizers, several approaches, also of a quite diverse nature, have been proposed to find good or provably good solutions, which makes it also very interesting as a benchmark problem for new algorithmic ideas. In this short course we review the most successful solution methods proposed for this problem along with the structural properties on which they are based. Max-Cut is also known to be equivalent to Unconstrained Quadratic Binary Optimization, i.e., to the problem of minimizing a quadratic form in binary variables. We also discuss the extensions to the case where instead of a quadratic form we consider a polynomial of degree higher than two.