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.

Filter by
Sorted by
Tagged with
39 votes
3 answers
5k views

Max-cut with negative weight edges

Let $G = (V, E, w)$ be a graph with weight function $w:E\rightarrow \mathbb{R}$. The max-cut problem is to find: $$\arg\max_{S \subset V} \sum_{(u,v) \in E : u \in S, v \not \in S}w(u,v)$$ If the ...
Aaron Roth's user avatar
  • 9,900
13 votes
4 answers
837 views

A Multi-cut Problem

I'm looking for a name or any references to this problem. Given a weighted graph $G = (V, E, w)$ find a partition of the vertices into up to $n = |V|$ sets $S_1,\ldots,S_n$ so as to maximize the ...
Aaron Roth's user avatar
  • 9,900
9 votes
1 answer
336 views

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
2 answers
1k views

Approximation algorithms for MAX-CUT, when sizes of partition sets are fixed

The MAX-CUT problem has constant factor approximation, but we can't control the sizes of the sets in resulting partition. What is known about maximizing cut size, if we restrict one part of the ...
Grigory Yaroslavtsev's user avatar
8 votes
1 answer
803 views

Is MAX CUT approximation resistant?

CSP optimization problem is approximation resistant if it is $NP$-hard to beat the approximation factor of a random assignment. For instance, MAX 3-LIN is approximation resistant since a random ...
Mohammad Al-Turkistany's user avatar
3 votes
1 answer
90 views

Deciding if max-cut with negative edge weights has a solution with positive value

I am interested in the complexity of the decision problem whether max-cut with positive and negative edge weights has a solution with positive value: Given a graph $G=(V, E)$ and edge weights $w: E \...
badboul's user avatar
  • 77