0
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you very much $\endgroup$ Commented Jul 2, 2022 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.