For a graph

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

, a maximum cut is a cut

Cut (graph theory)

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. The cut-set of the cut is the set of edges whose end points are in different subsets of the partition. Edges are said to be crossing the cut if they are in its cut-set.In an unweighted undirected graph, the...

 whose size is at least the size of any other cut. The problem of finding a maximum cut in a graph 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.

There is a more advanced version of the problem called weighted max-cut. In this version each edge has a real number, its weight, and the objective is to maximize not the number of edges but the total weight of the edges between S and its complement. The weighted max-cut problem is often, but not always, restricted to non-negative weights, because negative weights can change the nature of the problem.

Computational complexity

The following decision problem

Decision problem

In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...

 related to maximum cuts has been studied widely in theoretical computer science

Theoretical computer science

Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....

:

Given a graph G and an integer k, determine whether there is a cut of size at least k in G.

This problem is known to be NP-complete

NP-complete

In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...

. It is easy to see that problem is in NP

NP (complexity)

In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...

: a yes answer is easy to prove by presenting a large enough cut. The NP-completeness of the problem can be shown, for example, by a transformation from maximum 2-satisfiability (a restriction of the maximum satisfiability problem

Maximum satisfiability problem

In computational complexity theory, the Maximum Satisfiability problem is the problem of determining the maximum number of clauses, of a given Boolean formula, that can be satisfied by some assignment...

). The weighted version of the decision problem was one of Karp's 21 NP-complete problems

Karp's 21 NP-complete problems

One of the most important results in computational complexity theory was Stephen Cook's 1971 demonstration of the first NP-complete problem, the boolean satisfiability problem...

; Karp showed the NP-completeness by a reduction from the partition problem

Partition problem

In computer science, the partition problem is an NP-complete problem. The problem is to decide whether a given multiset of integers can be partitioned into two "halves" that have the same sum...

.

The canonical optimization variant

Optimization problem

In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete...

 of the above decision problem is usually known as the maximum cut problem or max-cut problem and is defined as:

Given a graph G, find a maximum cut.

Polynomial-time algorithms

As the max-cut problem is NP-hard, no polynomial-time algorithms for max-cut in general graphs are known. However, a polynomial-time algorithm to find maximum cuts in planar graph

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...

s exists.

Approximation algorithms

There is a simple randomized

Randomized algorithm

A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...

 0.5-approximation algorithm

Approximation algorithm

In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...

: for each vertex flip a coin to decide to which half of the partition to assign it. In expectation, half of the edges are cut edges. This algorithm can be derandomized with the method of conditional probabilities

Method of conditional probabilities

In mathematics and computer science, the probabilistic method is used to prove the existence of mathematical objects with desired combinatorial properties. The proofs are probabilistic — they work by showing that a random object, chosen from some probability distribution, has the desired properties...

; therefore there is a simple deterministic polynomial-time 0.5-approximation algorithm as well. One such algorithm is: given a graph start with an arbitrary partition of V and move a vertex from one side to the other if it improves the solution until no such vertex exists. The number of iterations is bound by because the algorithm improves the cut value by at least 1 at each step and the maximum cut is at most . When the algorithm terminates, each vertex has at least half its edges in the cut (otherwise moving to the other subset improves the solution). Therefore the cut is at least .

The best known max-cut algorithm is the …-approximation algorithm by Goemans and Williamson using semidefinite programming

Semidefinite programming

Semidefinite programming is a subfield of convex optimization concerned with the optimization of a linear objective functionover the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron....

 and randomized rounding

Randomized rounding

Within computer science and operations research,many combinatorial optimization problems are computationally intractable to solve exactly ....

. It has been shown by Khot et al that this is the best possible approximation ratio for Max-Cut assuming the unique games conjecture

Unique games conjecture

In computational complexity theory, the Unique Games Conjecture is a conjecture made by Subhash Khot in 2002. The conjecture postulates that the problem of determining the value of a certain type of game, known as a unique game, has NP-hard algorithmic complexity...

.

Inapproximability

The max-cut problem is APX-hard, meaning that there is no polynomial-time approximation scheme (PTAS), arbitrarily close to the optimal solution, for it, unless P = NP. Moreover, it has been shown NP-hard to approximate the max-cut value to better than ….

Assuming the unique games conjecture

Unique games conjecture

In computational complexity theory, the Unique Games Conjecture is a conjecture made by Subhash Khot in 2002. The conjecture postulates that the problem of determining the value of a certain type of game, known as a unique game, has NP-hard algorithmic complexity...

 (UGC), it is in fact NP-hard to approximate the max-cut value by a factor of for any , where … is the approximation factor of Goemans–Williamson. In other words, assuming the UGC and that , the Goemans–Williamson algorithm yields essentially the best polynomial-time-computable possible approximation ratio for the problem.

Maximum bipartite subgraph

A cut is a bipartite graph

Bipartite graph

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...

. The max-cut problem is essentially the same as the problem of finding a bipartite subgraph with the most edges.

Let be a graph and let be a bipartite subgraph of G. Then there is a partition (S, T) of V such that each edge in X has one endpoint in S and another endpoint in T. Put otherwise, there is a cut

Cut (graph theory)

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. The cut-set of the cut is the set of edges whose end points are in different subsets of the partition. Edges are said to be crossing the cut if they are in its cut-set.In an unweighted undirected graph, the...

in H such that the set of cut edges contains X. Therefore there is a cut in G such that the set of cut edges is a superset of X.

Conversely, let be a graph and let X be a set of cut edges. Then is a bipartite subgraph of H.

In summary, if there is a bipartite subgraph with k edges, there is a cut with at least k cut edges, and if there is a cut with k cut edges, there is a bipartite subgraph with k edges. Therefore the problem of finding a maximum bipartite subgraph is essentially the same as the problem of finding a maximum cut. The same results on NP-hardness, inapproximability and approximability apply to both the maximum cut problem and the maximum bipartite subgraph problem.

External links

• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger (2000), "Maximum Cut", in "A compendium of NP optimization problems".