I have a graph G (G=(V,E)), where each edge has a non negative weight to it.

My problem is to find a subset S (it doesn't have to exist) of nodes such the sum of all the weights of the edges that start in S and end in V\S is lower than a given positive k.

My approach was to pick a random node in the graph, run a bfs on a masked version of G where only the edges that are larger than k remain, and then check if each component of the masked G may be such S in G, if none may apply than ill conclude that no such S exists.

I calculated that this algorithm will have a run time of O(E^2 +V)

Now im finding a hard time to prove this algorithm is correct, but at the same time in struggling to find an example where it is incorrect.

Maybe someone could help me prove this algorithm is correct.


1 Answer 1


Your algorithm is incorrect. Let $G$ be a cycle on $4$ vertices where edge weights alternate between $2$ and $4$ and consider $k=5$.

The graph obtained from $G$ by keeping all and only the edges with weight larger* than $k$ contains no edges. Therefore the sets $S$ that you consider contain a single vertex.

Given any vertex, the sum of the weights of its incident edges is $6$. Therefore you conclude that the instance admits no solution. This is wrong since it is possible to choose $S$ so that the sum of edges crossing that cut is lower* than $k$ (in particular it is $4$).

*I have chosen the counterexample so that it holds even if any occurrence of "larger" and/or "lower" in the problem statement and in the proposed algorithm is optionally replaced with "at least" and "at most" (respectively).

  • $\begingroup$ Thank you very much $\endgroup$ Jul 2 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.