A max-cut approximation using a graph based MBO scheme

Keetch, Blaine; van Gennip, Yves

Abstract

© 2019 American Institute of Mathematical Sciences. All rights reserved. The Max-Cut problem is a well known combinatorial optimization problem. In this paper we describe a fast approximation method. Given a graph G, we want to find a cut whose size is maximal among all possible cuts. A cut is a partition of the vertex set of G into two disjoint subsets. For an unweighted graph, the size of the cut is the number of edges that have one vertex on either side of the partition; we also consider a weighted version of the problem where each edge contributes a nonnegative weight to the cut. We introduce the signless Ginzburg–Landau functional and prove that this functional Γ-converges to a Max-Cut objective functional. We approximately minimize this functional using a graph based signless Merriman–Bence–Osher (MBO) scheme, which uses a signless Laplacian. We derive a Lyapunov functional for the iterations of our signless MBO scheme. We show experimentally that on some classes of graphs the resulting algorithm produces more accurate maximum cut approximations than the current state-of-the-art approximation algorithm. One of our methods of minimizing the functional results in an algorithm with a time complexity of O(|E|), where |E| is the total number of edges on G.

Citation

Keetch, B., & van Gennip, Y. (2019). A max-cut approximation using a graph based MBO scheme. Discrete and Continuous Dynamical Systems - Series B, 24(11), 6091-6139. https://doi.org/10.3934/dcdsb.2019132

• Journal Article Type: Article
• Acceptance Date: Sep 19, 2018
• Publication Date: 2019-11
• Deposit Date: Mar 29, 2018
• Publicly Available Date: Dec 1, 2020
• Journal: Discrete and Continuous Dynamical Systems - Series B
• Print ISSN: 1531-3492
• Publisher: American Institute of Mathematical Sciences
• Peer Reviewed: Peer Reviewed
• Volume: 24
• Issue: 11
• Pages: 6091-6139
• DOI: https://doi.org/10.3934/dcdsb.2019132
• Public URL: https://nottingham-repository.worktribe.com/output/1125557
• Publisher URL: https://www.aimsciences.org/article/doi/10.3934/dcdsb.2019132