# Why isn't the Charikar algorithm for finding the densest subgraph optimal?

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?

• I am a little confused by the downvotes. Seems like a legitimate question. – 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.