Gadgets, gadgets, gadgets

One of the talks that deeply fall into my memory was the talk on this paper at ICALP 2011, where the authors show that some important problem is NP-hard, settling a 15-year-old open problem. The talk was exactly as you expected it to be: there were gadgets, and more gadgets, and more and more gadgets, until they stopped to fit into the slide. The tradition of such a talk on ICALP was maintained in 2012 by Dániel Marx with his Planar Multiway Cut lower bound.

Recently I spotted a list every TCSer should do in its career. I think that a point "publish a paper that consists solely of one humongous hardness reduction" is definitely missing there.

I miss a few points from the aforementioned list, but at least this new one would be satisfied with our this years SODA paper on Edge Clique Cover. Yes, there is only one huge reduction in this paper. It proves that, essentially, to solve the Edge Clique Cover problem exactly, you cannot do anything better than apply easy reductions and go brute-force.

In Edge Clique Cover we ask to cover the edges of a given graph with a minimum number of cliques that are its subgraphs. This is equivalent to saying that we want to compute an intersection model of a given graph with minimum size of the universe. There are a few easy reduction rules, such as "do the obvious thing with isolated vertices and isolated edges" or "identify twins, i.e., vertices v, u with N[v] = N[u]" (see here for details). If we ask for k cliques (k-element universe), these reductions bring the size of the graph down to 2k. A brute-force algorithm runs in time exponential in the size of the graph, which gives double-exponential dependency on k.

We show a reduction that reduces (in polynomial time) an n-variable 3CNF-SAT formula to a Edge Clique Cover instance with k=O(log n). This shows that any significant improvement upon the brute-force algorithm on the reduced instance would yield a subexponential algorithm for 3CNF-SAT, which seems unlikely.

The key idea of our reduction is to use the cocktail party graph as the main gadget. While it has got a plenty of edge clique covers of size O(log n), the known reductions are not able to reduce it.

So, if you'll attend SODA'13 and you like to see some slides filled with gadgets, don't miss Michal's talk on our paper.

Leave a Reply

Your email address will not be published. Required fields are marked *