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.
43
questions
0
votes
0
answers
52
views
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 ...
- 11
1
vote
0
answers
43
views
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 ...
- 11
0
votes
0
answers
137
views
When does the 'Overlap Gap' property not hold?
The overlap gap property describes problems where good solutions form clusters, so that 2 good solutions are either very close or very far. Problems having this property are problematic for ...
1
vote
0
answers
175
views
Easier famility of graphs for MAXCUT [closed]
I would like to know if there are particular family of graphs for which the Goemans-Williamson MAXCUT Approximation Algorithm renders higher than 0.878 approximation ratio. TIA
- 643
1
vote
1
answer
301
views
State of the art approximation algorithm for $\text{MAXCUT}$ that does better than Goemans and Williamson
I had thought that the Goemans-Williamson approximation algorithm was the best for MAXCUT. To quote from Wikipedia:
The polynomial-time approximation algorithm for Max-Cut with the best
known ...
- 173
6
votes
0
answers
362
views
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 ...
- 643
2
votes
0
answers
98
views
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. "...
- 643
2
votes
1
answer
246
views
Minimum cut with size bounds $k\leq |S| \leq |V|-k$
It is known by the max flow min cut theorem that the minimum cut problem is in $P$.
I am interested in knowing what is known on the complexity of the minimum cut with size $k\leq |S| \leq , |V|- k$. ...
- 1,058
-4
votes
1
answer
157
views
Partition vertices of graph into two sets such that there are at least $k$ edges between sets [closed]
I have to show that for every integer $k$, the problem whether the vertices of input graph can be partitioned into two sets such that there are a least $k$ edges between the sets can be solved in ...
- 1
2
votes
1
answer
163
views
Sum-of-Squares Certificates
We say that $f$ has a degree $2d$ sum-of-squares certificate if $f=\sum_{i=1}^r (g_i(x))^2$, where for each $i\in[r]$, we have that $g_i$ is a polynomial of degree at most $d$. Thus showing that $f$ ...
- 53
2
votes
1
answer
319
views
MaxCut instance with smallest max cut
Let us look at all 4-regular undirected graphs with $n$ nodes and edge weight equals to 1 for all edges. Out of these graphs, I would like to find the MaxCut instance with least number of edges in its ...
- 21
4
votes
1
answer
398
views
Intuitive explanation behind Goemans-Williamson randomized rounding
A very simple randomized cut algorithm achieves $1/2$ of the optimal value: just choose each vertex to be in the cut with probability $1/2$, independently. Goemans-Williamson does something more ...
- 10.2k
2
votes
1
answer
91
views
Weighted Min-Cut in bounded-genus graphs
What is the status of the following decision problem ?
Input : A graph $G=(V,E)$ embedded in a torus (or more generally a surface of genus $g$), a weight function $w:E \rightarrow \{-1,1\}$
Output : ...
- 475
4
votes
1
answer
221
views
Complexity of finding Exact Size Cut-Sets in Bipartite Graphs
I am interested in the problem of deciding if a cut-set of a given size $k$ (i.e. the number of edges crossing the partitions is $k$) exists in a given bipartite graph (both the graph and $k$ are part ...
- 71
3
votes
1
answer
181
views
SOS hardness of $Max-2-Lin(\mathbb{Z}_2)$?
Do we know of instances of $Max-2-Lin(\mathbb{Z}_2)$ which have a integrality gaps w.r.t to high degree (> 4) SOS relaxations?
Or if we specialize to Max-CUT do we know of graphs whose Max-CUT ...
- 1,443
-2
votes
1
answer
1k
views
Is the max cut problem still NP-Complete for graphs with unit weights on the edges? [closed]
We know that finding a max cut for weighted graphs is NP-Complete. I am trying to find a proof showing that even for graphs with just unit weights (every edge has weight 1) it is still NP-Complete.
I'...
7
votes
0
answers
250
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 ...
- 71
2
votes
2
answers
107
views
Name of graph partition that balances edges between sets with edges remaining within sets
Is there a common name for this problem:
Let G=(V, E) be an undirected graph. Partition V into sets $S_1$, $S_2$, ..., $S_k$, such that (the number of edges between sets) + (the number of "non"-...
- 123
7
votes
0
answers
3k
views
Reduction from Vertex Cover to Max-Cut? [closed]
I am referring to Computational Complexity by Arora and Barak for my course. In the section on NP-completeness reductions, the book has a diagram that is represents how one NP-complete problem ...
- 227
5
votes
0
answers
121
views
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}$...
- 1,224
8
votes
0
answers
111
views
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 ...
- 181
2
votes
1
answer
813
views
Max flow: either saturate an edge or avoids
Is there a way to create a max flow graph such that it satisfies the condition that a flow either saturates an edge or completely avoids it. It can't have half its flow through one edge and half ...
- 313
9
votes
1
answer
423
views
A purely graph-theoretic explanation of the reduction from Unique Label Cover to Max-Cut
I am studying the Unique Games Conjecture and the famous reduction to Max-Cut of Khot et al. From their paper and elsewhere on the internet, most authors use (what to me is) an implicit equivalence ...
- 1,318
21
votes
2
answers
982
views
Max-Cut algorithm that shouldn't work, unclear why
OK, this might seem like a homework question and, in a sense, it is. As a homework assignment in an undergraduate algorithms class, I gave the following classic:
Given an undirected graph $G=(V,E)$, ...
- 794
-2
votes
2
answers
214
views
MAX Cut with an oracle
Suppose that I have a MAX CUT problem on a weighted undirected Graph $G$, but there is an oracle that tells me what the value of the MAX CUT is, but not which edges produce it. Does this make the ...
- 101
5
votes
1
answer
319
views
Best approximation for a HYPERGRAPH-MAXDICUT problem
Consider a $(c^a,(c+d)^a,1)$-regular directed hypergraph $\mathcal{H}(a)$ on $n^a$ vertices with fixed $n\geq c+d+1$, fixed $c\geq 2$, fixed $d\geq 0$ and variable parameter $a\geq 1$ (meaning every ...
4
votes
2
answers
1k
views
Size of MAXCUT from eigenvalues
Is there an interpretation of MAXCUT using eigenvalues of the graph that yields constant factor approximation to MAXCUT?
Can the estimates provide sharp lower bound to MAXCUT?
- 12.7k
2
votes
1
answer
121
views
partition to min the max number of intersections
Given $n$ items and $m$ customers, each of whom is interested in some subset of the items, partition the set of items among $k$ different stores so that the maximum number of customers visiting any ...
- 21
3
votes
1
answer
331
views
What is this matrix column-selection problem, and how hard is it to approximate?
I ran across the following simple-to-state problem involving selection of a subset of columns simultaneously for a number of matrices. I suspect it might be well known, though I can't seem to place it....
- 575
8
votes
3
answers
935
views
Hardness of MAX-CUT on sparse graphs
Let a weighted graph $G(V,E)$, where the weights are real (positve and negative). Assume that $G$ has $\mathcal{O}(n\log n)$ edges.
How fast can we compute MAX-CUT on this graph?
Can we compute (...
- 1,346
9
votes
1
answer
713
views
Is Max-Cut APX-complete on triangle-free graphs?
In the Max-Cut problem, one seeks a subset S of vertices of a given simple undirected graph such that the number of edges between S and the complement of S is as large as possible.
Max-Cut is APX-...
- 945
3
votes
0
answers
223
views
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 ...
- 31
3
votes
1
answer
1k
views
Max-cut via linear programming or sdp
I am looking for a linear programming formulation for the max-cut problem. My interest is to know about the primal - dual algorithm for max-cut. It would be nice if someone can tell me that what is ...
- 725
3
votes
0
answers
159
views
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 ...
- 573
12
votes
2
answers
516
views
Euclidean-squared max-cut in low dimensions
Let $x_1, \ldots, x_n$ be points in the plane $\mathbb{R}^2$. Consider a complete graph with the points as vertices and with edge weights of $\|x_i - x_j\|^2$. Can you always find a cut of weight that ...
- 121
11
votes
1
answer
445
views
Examples of hard instances for Goemans and Williamson algorithm
I'm interested in the explicit examples of graphs for which application of Goemans and Williamson algorithm for approximating maximum cuts results in 0.878…-approximation factor.
The algorithm to ...
- 537
9
votes
1
answer
4k
views
What's the approximation factor of this Max k-Cut approximation?
I'm thinking about an approximation algorithm for Max k-Cut. One simple and more involved approximation algorithms can be found here. The Max k-Cut problem is defined as follows.
Input is a graph G = ...
- 3,440
10
votes
1
answer
1k
views
$\epsilon$-nets with respect to the cut norm
The cut norm $||A||_C$ of a real matrix $A = (a_{i,j}) \in \mathcal{R}^{n\times n}$ is the maximum over all $I \subseteq [n], J \subseteq [n]$ of the quantity $\left|\sum_{i \in I, j \in J}a_{i,j}\...
- 9,850
4
votes
0
answers
218
views
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 ...
- 20.8k
8
votes
1
answer
783
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 ...
- 20.8k
12
votes
3
answers
779
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 ...
- 9,850
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 ...
- 1,468
37
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 ...
- 9,850