A combinatorial algorithm for finding maximum cuts

Introduction

Finding the maximum cut of a graph is a difficult to compute problem in combinatorial optimization with several applications in the world of engineering and physics. This research develops and evaluates an exact branch and bound algorithm for the maximum cut of unweighted graphs that is designed for improved performance on sparse graphs.

The module provides a general overview of the problem along with necessary mathematical background in "The Maxcut Problem" and a brief note on various approaches to the problem in "Several Algorithms" . "A New Algorithm" describes a new algorithm for finding maximum cuts. Results of empirical performance evaluation appear in "Empirical Testing" , which "Conclusion" further discusses.

The maxcut problem

Before discussing the maxcut problem, it is necessary to provide some background information regarding relevant concepts in graph theory, the most fundamental of which is the graph itself. A graph $G(V,E)$ is an ordered pair comprised of a set of vertices V and a set of edges E that connect pairs of distinct vertices in V . Two examples are shown in [link] . Graphs may be either weighted, in which a real value is assigned to each edge, or unweighted, in which all edges have equal value. Although the former is more broadly applicable, further discussion will focus almost exclusively on the latter.

Unsurprisingly, a subgraph $G_1(V_1,E_1)$ of graph $G(V,E)$ is a graph with vertex set $V_1\subseteq V$ and edge set $E_1\subseteq E$ . Of particular usefulness will be the subgraph of $G(V,E)$ induced by a given set of edges $E_1\subseteq E$ , known as edge induced subgraph, which consists of that given set of edges E ₁ along with all vertices $V_1=\left\{v|(u,v)\in ,E_1,,,u,\in ,V\right\}$ that occur as an endpoint of at least one edge in E ₁ . An example of an edge induced subgraph is shown in [link] .

One class of graphs that will be especially important to discussion of the maxcut problem is bipartite graphs. A graph $G(V,E)$ is bipartite, like the example in [link] , if there are sets $V_1,V_2\subseteq V$ such that $V_1\cup V_2=V$ , $V_1\cap V_2=\varnothing$ , and $(u,v)\in E$ only if $u\in V_1,v\in V_2$ or $v\in V_1,u\in V_2$ . Additionally, a graph is bipartite if and only if it has no subgraph that is a cycle of odd length.

A cut of a graph can be informally understood and visualized as a closed curve crossing some realization of the graph where each edge can be crossed at most once, as seen in [link] . Notice that the curve partitions the graph vertices into two disjoint subsets located to each side of the curve.