Maximum cut problem: new models

Hakan Kutucu, Firdovsi Sharifov


In the paper, we present the maximum cut problem as maximization of a non-smooth convex function over polytope which is the convex hull of bases of the polymatroid associated with a submodular function defined on the subsets of node set of a given graph. We also formulate other new models for this problem and give necessary and enough conditions on an optimal solution in terms of network flow.


Convex function; bases of polymatroid; submodular function; network

Full Text:



Karp, R.M. (1972). Reducibility among combinatorial problems. In: R.E. Miller and J.W. Thatcher, eds. Complexity of Computer Computations. Plenum Press, 85-103.

Garey, M.R., Johnson, D.S., & Stockmeyer, L. (1976). Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3), 237-267.

Garey, M.R., & Johnson, D.S. (1979). Computers and Intractability: A Guide to theTheory of NP-Completeness. W.H. Freeman and Company.

Rendl, F., Rinaldi, G., & Wiegele, A. (2010). Solving MAX-CUT to optimality by intersecting semidefinite and polyhedral relaxations. Mathematical Programming, 121(2), 307-335.

Boros, E., & Hammer, P.L. (2002). Pseudo-Boolean optimization. Discrete Applied Mathematics, 123(1), 155-225.

Goemans, M., &Williamson, D.P. (1995). Improved approximation algorithms for MAXCUT and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6), 1115-1145.

Bertoni, A., Campadelli, P. & Grossi, G. (2001). An approximation algorithm for the maximum cut problem and its experimental analysis. Discrete Applied Mathematics, 110(1), 3-12.

Ben-Ameur, W., Mahjoub, A.R., & Neto, J.(2014). The maximum cut problem. In: V.T. Paschos, ed. Paradigms of Combinatorial Optimization: Problems and New Approaches, 2nd Edition, J. Wiley and Sons, 131-172.

Orlova, G.I., & Dorfman, Y.G. (1972). Finding the maximum cut in a graph. Engineering Cybernetics, 10(3), 502-506.

Hadlock, F.O. (1975). Finding a maximum cut of a planar graph in polynomial time. SIAM Journal on Computing, 4(3), 221-225.

Gr¨otschel, M., & Pulleyblank, W.R. (1981). Weakly bipartite graphs and the max-cut problem. Operations Research Letters, 1(1), 23-27.

Barahona, F. (1983). The max-cut problem in graphs is not contractible to K5. Operations Research Letters, 2, 107-111.

Chaourar, B. (2017). A Linear Time Algorithm for a Variant of theMAX CUT Problem in Series Parallel Graphs. Advances in Operations Research, 2017, 1-4.

Fujishige, S. (2005). Submodular Function and Optimization. Annals of Discrete Mathematics, 2nd ed. Elsevier Science, Amsterdam.

Nemhauser, G. & Wolsey, L.A. (1998). Combinatorial Optimization. Wiley-Interscience, New York.

Iwata, S. (2008). Submodular function minimization. Mathematical Programming, 112(1), 45-64.

Bazaraa, M.S., Sherali, H.D., & Shetty, C.M. (2006). Nonlinear programming: Theory and Algorithms. 3rd ed. John Wiley and Sons, New York.

Sharifov, F.A. (2018). Finding the maximum cut by the greedy algorithm. Cybernetics and Systems Analysis, 54(5), 737-743.



  • There are currently no refbacks.

Copyright (c) 2020 Hakan Kutucu, Firdovsi Sharifov

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.


   ithe_170     crossref_284         ind_131_43_x_117_117  Scopus  EBSCO_Host    ULAKBIM    PROQUEST   ZBMATH more...