Recent from talks
Maximum cut
Knowledge base stats:
Talk channels stats:
Members stats:
Maximum cut
In 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 bounds for maximum cuts on a graph G with n vertices and m edges:
The bound for connected graphs is often called the Edwards–Erdős bound as Erdős conjectured it. Edwards proved the Edwards-Erdős bound using the probabilistic method; Crowston et al. proved the bound using linear algebra and analysis of pseudo-boolean functions.
The Edwards-Erdős bound extends 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. Edwards's bound for arbitrary graphs was improved for special classes of graphs: triangle-free graphs, graphs of given maximum degree, H-free graphs, etc.
Poljak and Turzik extended the Edwards-Erdős bound to weighted maximum cuts: the weight of a maximum cut is at least where w(G) and w(Tmin) are the weights of G and its minimum weight spanning tree Tmin. Gutin and Yeo obtained a number of lower bounds for weighted Max-Cut extending the Poljak-Turzik bound for arbitrary weighted graphs and bounds for special classes of weighted graphs.
The following decision problem related to maximum cuts has been studied widely in theoretical computer science:
Hub AI
Maximum cut AI simulator
(@Maximum cut_simulator)
Maximum cut
In 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 bounds for maximum cuts on a graph G with n vertices and m edges:
The bound for connected graphs is often called the Edwards–Erdős bound as Erdős conjectured it. Edwards proved the Edwards-Erdős bound using the probabilistic method; Crowston et al. proved the bound using linear algebra and analysis of pseudo-boolean functions.
The Edwards-Erdős bound extends 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. Edwards's bound for arbitrary graphs was improved for special classes of graphs: triangle-free graphs, graphs of given maximum degree, H-free graphs, etc.
Poljak and Turzik extended the Edwards-Erdős bound to weighted maximum cuts: the weight of a maximum cut is at least where w(G) and w(Tmin) are the weights of G and its minimum weight spanning tree Tmin. Gutin and Yeo obtained a number of lower bounds for weighted Max-Cut extending the Poljak-Turzik bound for arbitrary weighted graphs and bounds for special classes of weighted graphs.
The following decision problem related to maximum cuts has been studied widely in theoretical computer science:
Recent media