This post is based on an expository explanation of iterative compression that I attempted at the Institute Seminar Week in 2010, at IMSc.
Tapesh has been struggling lately with the dire task of undergraduate homework. He has been asked to find a (vertex cover)[http://en.wikipedia.org/wiki/Vertex_cover] on 23 vertices - not one more - in a graph that has a thousand vertices. Being the straightforward boy, Tapesh considers writing a program that will try its luck on every possible subset of 23 vertices.
He then heads over to Wolfram Alpha to check how long it will be before he’s done, assuming (rather liberally) that he has at his disposal a computer that can perform $10^{24}$ operations per second.
It turns out that he, and more critically, his professor, would be in for a long, long wait. The algorithm would need time proportional to the age of the universe many times over, and this is decidedly depressing, particularly when one’s expected lifespan appears to be determined by the deadline for turning in homework.
Tapesh now appeals to his very clever cousin, Prodosh, for help.
Prodosh borrows the monstrous graph, and in short order, points out a vertex cover on 24 vertices, using powers evidently beyond what processors with $10^{24}$ FLOPS can do. Tapesh is thrilled, however…
“I need to get one with 23, the assignment says not one more —”
“Time for a smoke,” Prodosh yawns, and then delves into a distracted, pensive mood, with no signs of immediate return.
Tapesh is torn, but he decides to (gulp) show whatever he has so far - after all, it is progress!
Predictably, Professor Maganlal displays no signs of being impressed, but he grudgingly admits that Tapesh’s solution (which we will call $T$) is not very far from the correct answer, and points out those vertices in $T$ that happen to partake in the solution that was sought.
Tapesh is back to the drawing board, but with the distinct feeling that he is now armed with enough information to crack the code himself.
His solution $T$ is now partitioned into the good part $(T_G)$, that is, all the vertices of $T$ that belong to $X$, and the bad part $(T_B)$, which are all the vertices that do not belong to $X$.
“Aha.”
Necessarily, all the neighbors of the bad part must belong to $X$!
He checks, and sure enough, the number of vertices in $T_G$ and $N(T_B)$ is an exact, resounding 23. Also, very fortunately, there are no edges in $T_B$, so he has no trouble swapping $T_B$ for $N(T_B)$ to get to the newer and smaller vertex cover.
Mission accomplished!
Now more confident, Tapesh wonders if he could have arrived at $X$ all on his own. Indeed, what would he have done without Pradosh’s help? And without Professor Maganlal giving him that partition?
Come to think of it, the second question has an easy answer. Tapesh would just try all possible partitions of the solution that Pradosh had given him. He would only have to disregard the partitions that didn’t work… and sooner or later, he would hit the one that his Professor so graciously suggested. This would mean examining $2^{24}$ subsets, a matter of a split second for a personal computer.
But - can he replicate Pradosh’s magic on his own?