Finding local Max-Cut in graphs in randomized polynomial time

A maximum cut (Max-Cut) problem in graph theory is NP-hard. This paper proposes a new randomized algorithm for finding local Max-Cut in graphs by using fuzzy logic. This paper proves that: (1) the computational complexity of computing local Max-Cut in graphs is in the class of randomized polynomial time (RP); (2) the real number solution of the new algorithm satisfies epsilon - delta condition; (3) local Max-Cut solutions are maintained after defuzzification that converts real number vectors to integer vectors. Numerical experiments show that the new algorithm outperforms IBM CPLEX solvers. The new algorithm is nine times faster than the CPLEX Convex solver and more than thirty times faster than the CPLEX Global solver. The new algorithm could find local Max-Cut in signed graphs whereas CPLEX Convex solver failed to find Max-Cut in signed graphs when Laplacian matrix was not positive semidefinite.

Automated summary

This paper proposes a new randomized algorithm that uses fuzzy logic to solve the local Max-Cut problem in graphs. The paper proves the computational complexity and effectiveness of the algorithm and demonstrates its superiority over IBM CPLEX solvers, especially in signed graphs.