Skip to main content

Questions tagged [max-cut]

For a graph, a maximum cut is a cut 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.

10 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9 votes
1 answer

Positive cut algorithm on bipartite graphs with negative weights

Let $G=(V,E,w)$ be a bipartite graph with weight function $w:E→\{-1,1\}$. Is there an efficient (polynomial) algorithm for finding some positive (not necessarily maximum) cut of $G$, if one exists? If ...
curl-up's user avatar
  • 91
8 votes
0 answers

Approximating a max-cut's intersection with other cuts

For the purposes of this question, a cut in a graph $G$ is the edge-set $\delta (S)\subseteq E(G)$ between some vertex-set $S$ and its complement. A max cut is one with at least as many edges as any ...
Ross Churchley's user avatar
6 votes
0 answers

Fastest exact algorithm for MAXCUT

Is the algorithm introduced in the following paper still the fastest exact algorithm for general MAXCUT problems? TIA Ryan Williams, A new algorithm for optimal $2$-constraint satisfaction and its ...
Omar Shehab's user avatar
5 votes
0 answers

The distribution on the solution space induced by randomized rounding

Consider the Goemans-Williamson algorithm for the MAX-CUT problem. It is known, that if $maxcut(G) \geq 1-\epsilon$, then the algorithm returns a cut $S$ of fractional size at least $1-\sqrt{\epsilon}$...
Lior Eldar's user avatar
  • 1,224
4 votes
0 answers

Complexity of Max Bisection on cubic planar graphs?

Max Bisection problem is to partition the set of nodes into two equal size sets such that the number of crossing edges is maximum. Max Bisection is $NP$-complete on cubic graphs and also on planar ...
Mohammad Al-Turkistany's user avatar
3 votes
0 answers

The Quality of SDP relaxation on MaxCut

My question is: given a maxcut instance, if it costs too much to solve it to optimal practically but we can get an optimal solution of SDP relaxation quickly, can we assess the quality of this SDP ...
Ben's user avatar
  • 31
3 votes
0 answers

Gram matrix of Max-Cut relaxation

It seems that Goemans and Williamson give a unique representation for each graph of the semidefinite relaxation (elements $y_{ij}$ of Y). However, semidefinite programming may give the same maximum ...
N27's user avatar
  • 573
2 votes
0 answers

Resource on phase transition in MAXCUT problems

Could anyone suggest reading materials on phase transition in MAXCUT problems other than [1]? Thanks. Ref: Coppersmith, Don, David Gamarnik, Mohammad Taghi Hajiaghayi, and Gregory B. Sorkin. "...
Omar Shehab's user avatar
1 vote
0 answers

Max Flow Routing

Let G = (V,E,S,I,T) be a directed flow network with nodes V, edges E with unit capacity, source nodes S $\subseteq$ V, intermediate nodes I $\subseteq$ V, and target nodes T $\subseteq$ V. The problem ...
sripurva's user avatar
0 votes
0 answers

Prove that Vertex Cover is NP-Complete by reducing MaxCut to Vertex Cover

This is not the most straight forward reduction available on the internet since most people start from the fact that vertex cover is NP-complete and reduce a given vertex cover instance to MaxCut ...
Chaithanya's user avatar