The World’s Simplest Interesting Algorithm

In this post, I want to tell you about what I think might be the world’s simplest interesting algorithm.

The vertex cover problem. Given a graph ${G = (V, E)}$ , we want to find the smallest set of vertices ${S \subseteq V}$ such that every edge ${e \in E}$ is covered by the set ${S}$ . This means that for each edge ${e = (u, v)}$ , at least one of ${u}$ or ${v}$ is in ${S}$ .

The vertex cover problem is known to be NP-complete, meaning that it is very hard (or impossible) to find a polynomial-time algorithm for the problem.

But what we can do is find an approximately optimal solution to the problem. There’s a beautiful and simple algorithm that finds a set ${S}$ whose size is guaranteed to be within a factor of ${2}$ of optimal.

The algorithm. To build our set ${S}$ , we repeatedly find some edge ${e = (u, v)}$ that is not yet covered, and we add both ${u}$ and ${v}$ to our set ${S}$ . That’s the entire algorithm.

At first sight, this seems like a crazy algorithm. Why would we put both ${u}$ and ${v}$ into ${S}$ , when we only need one of ${u}$ or ${v}$ in order to cover the edge ${e = (u, v)}$ ?

The answer to this question is simple. If we define ${S_{\text{OPT}}}$ to be the optimal solution to the vertex-cover problem, then ${S_{\text{OPT}}}$ must contain at least one of ${u}$ or ${v}$ . By placing both of ${u}$ and ${v}$ into our set ${S}$ , we guarantee that at least half the elements in our set ${S}$ also appear in ${S_{\text{OPT}}}$ . That means that, once our algorithm finishes, we are guaranteed that ${|S| \le 2 |S_{\text{OPT}}|}$ .

A challenge. This might be the world’s simplest interesting algorithm (and analysis). But it also might not be. What do you think?