All Questions
Tagged with max-cut np-complete
3 questions
3
votes
1
answer
112
views
Deciding if max-cut with negative edge weights has a solution with positive value
I am interested in the complexity of the decision problem whether max-cut with positive and negative edge weights has a solution with positive value:
Given a graph $G=(V, E)$ and edge weights $w: E \...
- 187
4
votes
1
answer
255
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
-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'...
