I read about the algorithm in Greedy Approximation Algorithms for Finding Dense Components in a Graph by Moses Charikar, and I tried to find an instance/graph where the algorithm returns a different solution from the optimal one but I didn't succeed. Can anyone provide me an example where the algorithm 'fails' and proves that the approximation is no less than 2?

  • 5
    $\begingroup$ I am a little confused by the downvotes. Seems like a legitimate question. $\endgroup$ – Sasho Nikolov Nov 25 '17 at 22:24

Suppose you have a complete graph on four nodes and then next to it a graph with five nodes comprising a degree four hub and four degree 3 satellites. The greedy algorithm might start by removing one of the satellites and thus spoil the optimum which is 1.6 o-------o o-------o | \ / | | \ / | | X | | o | | / \ | | / \ | o-------o o-------o For the sake of completeness: given a graph $G=(V,E)$ the task is to find a subset $S\subseteq V$ maximising the quantity $|E(S)| / |S|$ where $E(S)\subseteq E$ is the set of edges with endpoints in $S$. The greedy algorithm operates by successively removing vertices of minimal degree and then searching for the optimal $S$ among the successively shrinking set of remaining vertices.


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.