# 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
Filter by
Sorted by
Tagged with
1 vote
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 ...
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 ...
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 ...
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 vote
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 ...
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 ...
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 ...
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. ...
1 vote
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 ...
1 vote
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 ...
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, ...
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 ...
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 ...
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 ...
1 vote
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 ...
1 vote
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 ...
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 ...
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 ...
1 vote
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
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$ ...
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 ...
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 ...
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 ...
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 \...
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 ...
1 vote
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 ...
1 vote
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 ...
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 ...
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 ...