Maximum cut problem: new models

Abstract

The maximum cut problem is known to be NP-hard, and consists in deter-mining a partition of the vertices of a given graph such that the sum of theweights of the edges having one end node in each set is maximum. In thispaper, we formulate the maximum cut problem as a maximization of a simplenon-smooth convex function over the convex hull of bases of the polymatroidassociated with a submodular function defined on the subsets of vertices of agiven graph. In this way, we show that a greedy-like algorithm with O(mn2)time complexity finds a base of a polymatroid that is a solution to the maxi-mum cut problem with different approximation ratio. Moreover, with respectto a base of a polymatroid, we formulate the maximum cut problem as a max-imum flow problem between a source and a sink. We then investigate thenecessary and sufficient conditions on the optimality of the base in terms ofnetwork flow.