UPDF AI
New Chat
Search History
Scholar ResearchPaper SearchLibrary
Chats
UPDF AI

Finding local Max-Cut in graphs in randomized polynomial time

Lunshan Gao

2023 · DOI: 10.1007/s00500-023-09230-5
Soft Computing - A Fusion of Foundations, Methodologies and Applications · 1 Citations

TLDR

It is proved that the computational complexity of computing local Max-Cut in graphs is in the class of randomized polynomial time (RP); the real number solution of the new algorithm satisfies the ϵ - δ condition; and local Max-Cut solutions are maintained after defuzzification that converts real number vectors to integer vectors.

Abstract

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.