Questions tagged [max-cut]
Questions on the maximum cut problem, where one is given a graph and wants to find a subset of the vertex set such that number of edges between it and the complementary subset is as large as possible.
31
questions
1
vote
1
answer
99
views
Reduction from MAX-3-CUT to MAX-CUT
Both MAX-CUT and MAX-3-CUT are known to be NP-complete. This post shows a reduction from MAX-CUT to MAX-3-CUT. I am curious if there is a way to reduce MAX-3-CUT to MAX-CUT?
MAX-CUT: Given an ...
- 113
2
votes
1
answer
164
views
Min-cut with maximal number of edges
I’ve searched for a solution for this problem for some time now, it is out of an algorithm question sheet.
We know that in order to find the minimal amount of edges in a flow graph’s min-cut we need ...
- 315
3
votes
1
answer
112
views
Efficiently determine which nodes should leave a graph while maintaining connectedness
Suppose I have a graph with node weights, where a weight is either -1 or a positive integer. For example:
If a node has weight -1, it is "happy", and cannot be kicked out of the graph.
If a ...
- 133
0
votes
0
answers
124
views
Prove minimum vertex bisection problem is reducible from bisection width, thereby proving NP-Completeness
The bisection width problem gives you a yes or a no -> if there exists a bisection of size at most $K$ for $G=V,E$.
Minimum Vertex Bisection problem gives you a bisection of the smallest size.
...
- 1
1
vote
1
answer
63
views
Split a graph before actually creating it
Consider a weighted graph $G=(V,E)$ of vertex set $V = \{v_1, ..., v_n\}$ and weighted edge set $E = \{\langle v_i, v_j, w(i,j)\rangle \mid i, j \in 1, ..., n\}$, where $w$ is the function that assign ...
- 459
0
votes
1
answer
25
views
Maxcut problem of spatial embedding graphs
Given a graph $(V,E)$, I'm interested in embedding it into a Euclidean space $\mathbb{R}^n$ such that each vertex $v\in V$ becomes a point $x_v\in\mathbb{R}^n$ and $d(x_v,x_u) \leq 1$ (Euclidean ...
- 215
9
votes
1
answer
677
views
Spatial embedding of graph
Given a graph $(V,E)$, I'm interested in embedding it into a Euclidean space $\mathbb{R}^n$ such that each vertex $v\in V$ becomes a point $x_v\in\mathbb{R}^n$ and $d(x_v,x_u) \leq 1$ (Euclidean ...
- 215
0
votes
0
answers
64
views
Score and bound in Goemans-Williamson algorithm
I am trying to have a deeper understanding of the following implementation of the Goemans-Williamson algorithm for solving the maxcut problem.
...
- 326
1
vote
0
answers
38
views
Finding a cut maximizing average weight of cut edges
Just checking if this version of Max Cut is still NP-hard:
Given a fully connected graph $G(V,E)$, where every vertex is connected to every other vertex, and where every edge has a weight associated ...
- 13
1
vote
1
answer
88
views
How to find a cut in a graph with additional constraints?
I have a complete undirected graph $G=(V,E)$ with positive non-null rational weights $c:E \to \mathbb{Q}^+_{*}$ on the edges, such that $c(v,v) = 0$ for all $v$, and a subset $C \subset V$.
I would ...
3
votes
1
answer
976
views
Using a greedy algorithm to find a cut S which at least half of the edges cut
Let $G$ be an undirected graph.
Find a greedy algorithm that finds a cut $S$ which at least half of the edges cut.
I tried to think about something like choosing the vertex with the highest degree, ...
- 133
2
votes
1
answer
30
views
Separation guarantee in Goemans Williamson algorithm
In the original paper in Goemans-Williamson paper for max-cut, we need to sample a random vector r and
we output
$$
S = \{i : r^{T}x_{i} \geq 0\}
$$
where $x_{i}$ are column vector of a feasible ...
- 135
2
votes
0
answers
38
views
planar max cut graph with constrains
Given a planar graph $G=(V, E)$
I am looking for a max cut algorithm with the following conditions : some vertices are in one of the partition sets?
Is the algo is still polynomial ?
I mean a ...
- 21
9
votes
2
answers
937
views
Prove that the 2-approximation of a modified local search algorithm for max-cut is tight
Consider the following local search approximation algorithm for the unweighted max cut problem:
start with an arbitrary partition of the vertices of the given graph $G = (V,E) $, and as long as you ...
- 113
1
vote
1
answer
984
views
How can i prove that MAX-CUT is in NP?
How can i show/explain/prove that Max-Cut is in NP?
"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 ...
- 23
1
vote
1
answer
170
views
Derandomize MAX-CUT problem using $\log n$ bits
Consider the MAX-CUT problem. We can flip $n$ coins to generate a random cut, and by linearity of expectation we get that with "good probability" our cut we'll be bigger then $\frac{n}{2}$.
Using ...
- 327
2
votes
2
answers
397
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 ...
- 73
0
votes
1
answer
742
views
Reducing INDSET and MAXCUT to 3SAT
Given a graph and an integer $k$ is there an independent set larger than $k$ is INDSET problem and is there a cut larger that $k$ is the MAXCUT problem. Is there standard way to convert to 3SAT from ...
- 2,881
1
vote
2
answers
2k
views
Does graph G with all vertices of degree 3 have a cut vertex?
I'm asked to draw a simple connected graph, if possible, in which every vertex has degree 3 and has a cut vertex. I tried drawing a cycle graph, in which all the degrees are 2, and it seems there is ...
1
vote
0
answers
502
views
solving max cut problem on a huge graph (500 x 500) using Semidefinite Programming with CVXOPT
So I am learning to do SDP relaxation on graph problems, and for this max cut problem I am given a 500*500 graph, and I am using the straightforward
relaxation. $W$ is the weight matrix, $X = u u^T$ ...
- 11
3
votes
1
answer
261
views
Why the Goemans-Williamson's MAX-CUT algorithm relax the variables to vectors of $n-$dimension on unit sphere?
Why not to some constant like 3 or 4 dimension? I suspect that it is because Cholesky Decompostion will work only for $n \times n$ matrix $B$ where $B^TB = P$ where $P$ is a semidefinite matrix. Is it ...
- 187
3
votes
0
answers
724
views
Greedy max k-cut approximation algorithm
I'm trying to formulate a greedy algorithm for the Max k-cut problem:
Let's have an not oriented graph $G(V,E)$, each edge $e \in E$ has its weight $w_e$. The goal of the algorithm is to divide all ...
- 151
0
votes
2
answers
453
views
NP hardness of partitioning a graph into two subgraphs
Given a planner graph which it's vertexes have weights and an integer, W, this graph should be partitioned into two subgraphs which sum of weights for each subgraph becomes at least W.
I wanted to ...
- 125
3
votes
1
answer
6k
views
Maximum cut using a 1/2 approximation greedy algorithm
I have the following greedy algorithm for max cut problem:
Initialization: $A \leftarrow \{v_1\}$ , $B \leftarrow \{v_2\}$
For $v \in V − \{v_1, v_2\}$ do:
if $d(v,A) \geq d(v,B)$ then $B \...
- 125
2
votes
1
answer
1k
views
Maximum flow with edge demands: can't understand the example of transition to transformed graph in the lecture notes
TL;DR:
There're lecture notes about a very simple reduction from "maximum flow with edge demands problem to the maximum flow problem. But I can't get the new capacities at the picture:
E.g., look at ...
- 21
1
vote
1
answer
73
views
Maximum One Third Cut
I want to solve the following problem (This is a homework problem. Not looking for definite or complete answers):
Maximum One Third Cut:
Input: An undirected graph G=(V,E) where V={1,2,...,n}, such ...
- 167
1
vote
1
answer
593
views
Degree Reduction in Max Cut and Vertex Cover
I have been reading Alimonti and Kann's paper "Some APX-Completeness results for cubic graphs" and I don't understand why the degree-reduction gadgets for Max Cut and Min Vertex Cover have to be ...
- 127
2
votes
1
answer
617
views
Relation between MAX CUT and MIN CUT
I'd like to ask a question about MAX CUT and MIN CUT on graphs with unit edge-weight. I know that MAX CUT is NP-Hard, but MIN CUT is in P (i think)?
Barahona, in 1982, showed (Lemma 1) finding a cut ...
- 127
5
votes
1
answer
3k
views
Reduction from PARTITION to MAX-CUT
I am trying to prove the NP-Hardness of the MAX-CUT problem. Other sources seem to reduce from the NAE-3SAT problem, however I have been trying to reduce from PARTITION because PARTITION and MAX-CUT ...
- 193
5
votes
1
answer
224
views
What is the significance of the vector dimension in semidefinite programming relaxations?
Let's say that we want to design a semi-definite programming approximation for an optimization problem such as MAX-CUT or MAX-SAT or what have you.
So, we first write down an integer quadratic ...
- 339
5
votes
3
answers
1k
views
Maximum number of matched vertexes in a one-to-many bipartite graph
I have a variant of bidding problem at hand.
There are N bidders(~20) who bid for items from a pool of many items(~10K). Each bidder can bid many items. I want to maximize the number of bidders who ...
- 53