C&SA | Contents

Volume 56 >>> № 4 JULY — AUGUST 2020

UDC 519.8

F. Sharifov¹, L. Hulianytskyi²

¹ V.M. Glushkov Institute of Cybernetics, National Academy
of Sciences of Ukraine, Kyiv, Ukraine

² V.M. Glushkov Institute of Cybernetics, National Academy
of Sciences of Ukraine, Kyiv, Ukraine

CUTS IN UNDIRECTED GRAPHS. I

Abstract. This part of the paper analyzes new properties of cuts in undirected graphs, presents various models for the maximum cut problem, based on the established correspondence between the cuts in this graph and the specific bases of the extended polymatroid associated with this graph. With respect to the model, formulated as the maximization of the convex function on the compact set (extended polymatroid), it was proved that the objective function has the same value at any local and global maximum, i.e., to solve the maximum cut problem, it needs to find a base of the extended polymatroid as a local or global maximum of the objective function.

Keywords: graphs, cuts, convex function, special polyhedra.

FULL TEXT

REFERENCES

Barahona F., M., M., Reinelt G. An application of combinatorial optimization to statistical physics and circuit layout design. Operations Research. 1988. Vol. 36, N 3. P. 493–513.

Karp R.M. Reducibility among combinatorial problems. Miller R.E., Thatcher J.W., Bohlinger J.D. (Eds.). Complexity of Computer Computations. New York: Plenum Press, 1972. P. 85–103.

Garey M.R., Johnson D.S., Stockmeyer L. Some simplified -complete graph problems. Theoret. Comput. Sci. 1976. Vol. 1, Iss. 3. P. 237–267.

Garey M.R., Johnson D.S. Computers and intractability: A guide to the theory of -completeness. New York: W.H. Freeman and Company, 1979.

Boros E., Hammer P.L. Pseudo-Boolean optimization. Discrete Applied. Mathematics. 2002. Vol. 123, Iss. 1–3. P. 155–225.

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

Orlova G.I., Dorfman Y.G. Finding the maximal cut in a graph. Engineering Cybernetics. 1972. Vol. 10. P. 502–504.

Hadlock F.O. Finding a maximum cut of a planar graph in polynomial time. SIAM Journal on Computing. 1975. Vol. 4, Iss. 3. P. 221–225.

Shih K., Wu S., Kuo Y.S. Unifying maximum cut and minimum cut of a planar graph. IEEE Transactions on Computers. 1990. Vol. 39, Iss. 5. P. 694–697.

M., Pulleyblank W.R. Weakly bipartite graphs and the max-cut problem. Operat. Res. Lett. 1981. Vol. 1, Iss. 1. P. 23–27.

Barahona F. The max-cut problem in graphs is not contractible to . Operat. Res. Lett. 1983. Vol. 2, Iss. 3. P. 107–111.

Brahim Chaourar. A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs. 2017. Vol. 2017. Article ID 1267108. 4 p. https://doi.org/10.1155/2017/1267108.

Ben-Ameur W., Mahjoub A.R., Neto J. The maximum cut problem. In: Paradigms of combinatorial optimization. In Problems and New Approaches. Ch. 6. Paschos V.T. (Ed.). J. Wiley and Sons, USA, 2nd edition, 2014.

Poljak S., Tuza Z. Maximum cuts and large bipartite subgraphs. American Mathematical Society. 1995. Vol. 20. P. 181–244.

Goemans M.X., Williamson D.P. Improved approximation algorithms for MAX-CUT and satisfiability problems using semidefinite programming. Journal of ACM. 1995. Vol. 42, N 6. P. 1115–1145.

Rendl F., Rinaldi G., Wiegele A. Solving MAX-CUT to optimality by intersecting semidefinite and polyhedral relaxations. Math. Program. Publ. Online: May 6, 2008. 33 p. URL:

Sharifov F.A. Finding the maximum section of the grid algorithm. Kibernetika i sistemnyj analiz. 2018. Vol. 54, N 5. P. 48–54.

Stoer M., Wagner F. A simple min cut algorithm. Journal of ACM. 1997. Vol. 44, N 4. P. 583–591.

Iwata S. Submodular function minimization. Math. Program. Ser. A–B. 2008. Vol. 112, N 1. P. 45–64.

Bazaraa M.S., Sherali H.D., Shetty M.C. Nonlinear programming: Theory and algorithms. New York: J. Wiley and Sons, 1979. 583 p.