3
$\begingroup$

Let $G$ be an undirected graph.

Find a greedy algorithm that finds a cut $S$ which at least half of the edges cut.

I tried to think about something like choosing the vertex with the highest degree, add it to $S$, remove it from the graph and then repeat this process until I'm done.

However, this is nothing more than a guess and I could not prove it.

I tried to think of the problem in another way - removing no more than half of the edges in the graph until I get a bipartite graph, but finding the cycles takes too long.

Online solutions to this problem included using random algorithms - something we haven't learned in the course where I was handed this question. Other solutions were not clear to me (including one that was posted on this site), or seemed too complicated for the course level.

Could someone provide guidance please?

$\endgroup$
6
  • 2
    $\begingroup$ Tips on how to test your guess: cs.stackexchange.com/q/59964/755 $\endgroup$ – D.W. Jun 8 '20 at 20:07
  • $\begingroup$ @D.W. Thank you, but I am familiar with proving correctness of greedy algorithms. This specific problem I am having trouble with. $\endgroup$ – EL_9 Jun 8 '20 at 20:49
  • $\begingroup$ You said "this is nothing more than a guess and I could not prove it". Did you follow the techniques there? Did you implement it and test it on a bunch of randomly chosen test cases? $\endgroup$ – D.W. Jun 8 '20 at 22:00
  • $\begingroup$ I did try it out on a few exampled I made myself and it "worked" but proving correctness is the issue. The proof gets really ugly really fast, and I am sure there is a better algorithm. $\endgroup$ – EL_9 Jun 8 '20 at 22:26
  • $\begingroup$ a couple hints: as mentioned in the link above, a proof by contradiction is very often the most straightforward and cleanest way to prove an algorithm. Some advice that may or may not help you is to try to come up with an example that will BREAK your greedy algorithm. So, after your algorithm terminates, the graph is partitioned into two sets, and some local stopping condition is true for each vertex. Is it possible for these stopping conditions to be true for all vertices, and for the cut to contain less than half the edges? To help clarify, what do you mean by "until I'm done"? $\endgroup$ – Kevin Wang Jun 9 '20 at 0:05
3
$\begingroup$

List the vertices in some order, $v_1,\ldots,v_n$. Put $v_1$ in an arbitrary side of the cut. For each of the vertices $v_2,\ldots,v_n$, put it in the side of the cut which maximized the number of edges cut (only counting edges involving vertices which have already been processed). Since there are only two sides, each time you cut at least half the edges.

$\endgroup$

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.