A max-cut approximation using a graph based MBO scheme

Blaine Keetch, Yves van Gennip

Research output: Contribution to journalArticleScientificpeer-review

8 Downloads (Pure)

Abstract

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.

Original languageEnglish
Pages (from-to)6091-6139
Number of pages49
JournalDiscrete and Continuous Dynamical Systems - Series B
Volume24
Issue number11
DOIs
Publication statusPublished - 1 Nov 2019

Keywords

  • Ginzburg-Landau functionals
  • Graph algorithms
  • NP hard problems
  • Partial differential equations on graphs

Fingerprint Dive into the research topics of 'A max-cut approximation using a graph based MBO scheme'. Together they form a unique fingerprint.

Cite this