Share Your Experience: Take the 2024 Developer Survey

# 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.

33 questions
Filter by
Sorted by
Tagged with
84 views

### Max cut 2-approximation algorithm

Given an undirected unweighted graph $G$, we'll define $f(G)$ as the maximum number of edges crossing a cut in $G$. Find a (polynomial) 2-approximation for $f$. I know about the probabilistic method, ...
• 241
42 views

### Finding a Maximum Cut With Force Labeled Vertices for Planar Graphs

The maximum cut problem is a combinatorial optimization problem that seeks to partition the vertices of a graph into two sets, $S$ and $T$, in a way that maximizes the number of edges that cross ...
1 vote
127 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
232 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 ...
• 355
120 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
200 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
65 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 ...
• 551
28 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
688 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
69 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
41 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
98 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 ...
1k 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
31 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
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 ...
992 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
1k 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
179 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
526 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 ...
901 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,891
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
522 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
299 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 ...
754 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
466 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 ...
• 135
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 \...
• 135
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
77 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
607 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
659 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
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