Dear all,
I am working on a problem and I was wondering if you could help me to find an answer: We consider a complete graph with +1 or -1 edges (weights). We want to determine whether there is a sub-graph for which sum of the weights (edges) with the remaining sub-graph is less than 0. I want to know whether there is any polynomial algorithm for this problem.
Best Wishes, Morteza