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.

Filter by
Sorted by
Tagged with
1
vote
1answer
25 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 ...
0
votes
0answers
13 views

Does the weighted max cut problem have applications to machine learning? If so, what are they?

At first, I thought the weighted max cut problem (WMCP) could be of use to binary classifiers, but since the standard WMCP doesn't have any "node groups must be on opposite side of a straight line" ...
1
vote
1answer
25 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 ...
2
votes
2answers
157 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 ...
0
votes
1answer
119 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
2answers
494 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
0answers
190 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$ ...
1
vote
1answer
106 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 ...
2
votes
0answers
336 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 ...
0
votes
2answers
155 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 ...
2
votes
1answer
988 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
1answer
45 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
1answer
429 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 ...
2
votes
1answer
331 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 ...
2
votes
0answers
92 views

reduction of maxcut problem [duplicate]

Show that if the MAX CUT decision problem can be solved in polynomial time so can the MAX CUT optimization problem by writing an algorithm that solves the optimization problem using an algorithm for ...
4
votes
1answer
2k 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 ...
3
votes
1answer
114 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 ...
5
votes
3answers
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 ...