Let $G=(V,E,w)$ be a bipartite graph with weight function $w:E\{-1,1\}$. Is there an efficient (polynomial) algorithm for finding some positive (not necessarily maximum) cut of $G$, if one exists? If it is needed, we can presume that such cut exists (but sum of all weights may be negative).If not, is there such an algorithm when two nodes on the opposite sides of such cut are already provided?I am aware that this might be a duplicate of this question. I went through the given articles, but I am not sure if they answer my question. For example, I do not understand what the approximation performance means in the context of negative weights. If all but one cut have non-positive values, does that mean that the approximation algorithm will find that single positive solution (because only for that solution the performance condition is met)?
Positive cut algorithm on bipartite graphs with negative weights
ds.algorithms;graph theory;approximation algorithms;max cut