<p>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
<code>
o-------o    o-------o
| \   / |    | \   / |
|   X   |    |   o   |
| /   \ |    | /   \ |
o-------o    o-------o
</code>
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.  </p>

CC BY-SA 4.0
2023-12-10T19:57:45.213Z
Is this counterexample "tight"? i.e., does it show that 2 is indeed the best approximation ratio that the algorithm respects?
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2017-11-28T09:38:29.507Z
2017-11-28T12:31:41.263Z
2017-11-28T12:31:41.263Z
Martin Hofmann
<p>I read about the algorithm in
<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.121.1184&amp;rep=rep1&amp;type=pdf" rel="noreferrer">Greedy Approximation Algorithms for Finding
Dense Components in a Graph</a> 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?</p>

CC BY-SA 3.0
2017-11-25T22:24:06.940Z
I am a little confused by the downvotes. Seems like a legitimate question.
Sasho Nikolov
<graph-theory><graph-algorithms><approximation>
Why isn't the Charikar algorithm for finding the densest subgraph optimal?
Karapost
# Why isn't the Charikar algorithm for finding the densest subgraph optimal?

(Asked by: username_0 on 2017-11-24)

I read about the algorithm in
[Greedy Approximation Algorithms for Finding
Dense Components in a Graph](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.121.1184&rep=rep1&type=pdf) 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?

**Tags:** graph-theory, graph-algorithms, approximation

> **Comments:**
> **username_1**: I am a little confused by the downvotes. Seems like a legitimate question.  

---

## 1 answers

### Answer by username_2 on 2017-11-28. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_3**: Is this counterexample "tight"? i.e., does it show that 2 is indeed the best approximation ratio that the algorithm respects?  

---

