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?

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Tips on how to test your guess: cs.stackexchange.com/q/59964/755 $\endgroup$
    – D.W. ♦
    Jun 8, 2020 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, 2020 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, 2020 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, 2020 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, 2020 at 0:05

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

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

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