Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Maximum cut
Summary
For a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets S and T, such that the number of edges between S and T is as large as possible. Finding such a cut is known as the max-cut problem.
The problem can be stated simply as follows. One wants a subset S of the vertex set such that the number of edges between S and the complementary subset is as large as possible. Equivalently, one wants a bipartite subgraph of the graph with as many edges as possible.
There is a more general version of the problem called weighted max-cut, where each edge is associated with a real number, its weight, and the objective is to maximize the total weight of the edges between S and its complement rather than the number of the edges. The weighted max-cut problem allowing both positive and negative weights can be trivially transformed into a weighted minimum cut problem by flipping the sign in all weights.
Edwards obtained the following two lower bound for Max-Cut on a graph G with n vertices and m edges (in (a) G is arbitrary, but in (b) it is connected):
(a)
(b)
Bound (b) is often called the Edwards-Erdős bound as Erdős conjectured it. Edwards proved the Edwards-Erdős bound using probabilistic method; Crowston et al. proved the bound using linear algebra and analysis of pseudo-boolean functions.
The proof of Crowston et al. allows us to extend the Edwards-Erdős bound to the Balanced Subgraph Problem (BSP) on signed graphs G = (V, E, s), i.e. graphs where each edge is assigned + or –. For a partition of V into subsets U and W, an edge xy is balanced if either s(xy) = + and x and y are in the same subset, or s(xy) = – and x and y are different subsets. BSP aims at finding a partition with the maximum number b(G) of balanced edges in G. The Edwards-Erdős gives a lower bound on b(G) for every connected signed graph G.
Bound (a) was improved for special classes of graphs: triangle-free graphs, graphs of given maximum degree, H-free graphs, etc.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.