# Construct intractable instance of set cover

Choose an integer n and construct the set S with n elements. Then construct a set, s, of subsets of S such that finding the minimum subset of s (that minimises the sum of the orders of all chosen sets of s in that subset) the union of which covers S is computationally intractable on current hardware.

My question is how would one choose n and construct s such that finding a minimum (or to relax it a bit, an approximation to a minimum) set cover is computationally intractable?

I understand the greedy algorithm for set cover, but I don't understand how to explicitly create an intractable instance of this problem.

The greedy algorithm is to, at each iteration, select the member of s which covers the largest number of elements of S not already covered by previously selected members of s. Take the union of all of these selected members of s, until S is covered.

Also, by intractable I mean something like ' even running at 70 million set choices per second the greedy algorithm on such an instance would take 10**(F(n)) years ' where F is polynomial in n, or similar.

Also I don't understand what relevance this would have for anything else, it just occurred to me as interesting to know what the structure of such an intractable instance would look like.

-
What is "the greedy algorithm"? – joriki Dec 27 '12 at 14:16
Good point. Added. – Cris Stringfellow Dec 27 '12 at 14:17

You cannot hope to find a problem instance that is intractable for all algorithms, because for any problem instance you can come up with, there's an algorithm that checks whether the input is that specific instance, and if so outputs the right answer to that; otherwise it runs an exhaustive search.

So the best you can hope for is to find a family of problem instances such that they can't all be tractable by the same algorithm. To do this, start with a family of problems that we "know" is intractable itself, such as

Is there an AES-128 key whose first 24 bits are 298AF3 which encrypts 0123456789ABCDEF0123456789ABCDEF into 00112233445566778899AABBCCDDEEFF?

This had better be intractable, because if we could solve all problems of this general shape, AES would be quite broken -- just knowing one or two plaintext-ciphertext pairs would allow us to recover a key by running the solve 128 times.

Now we first express the AES problem as a Boolean circuit satisfiability problem. The unknown inputs to the circuit are the unspecified bits of the key; the circuit itself is simply the AES encryption primitive. As a rough estimate this should take somewhere in the range of 10.000 to 100.000 gates.

Then reexpress the Boolean circuit as a 3SAT problem, and use the standard reduction to make this into a Vertex Cover problem. Each of these rewritings entail a modest linear increase in size, so we end up with a graph of about half a million vertices.

Now, of course Vertex Cover is just a special case of Set Cover, so you can just read off a Set Cover instance from the graph -- $S$ is the set of edges in the graph, and each vertex becomes an element of $s$.

Bonus chatter: What "goes wrong" if we try to apply the greedy algorithm to a problem constructed in this way?

The way the 3SAT-to-VertexCover reduction works makes clear that a large portion of the sets in the final Set Cover instance will have size 3 -- namely those that arise from vertices that represent 3SAT clauses. The vertices that represent variables can have higher degree -- but they don't touch any other variable-representing vertices (except for their own dual) directly; all of the interaction between the high-degree vertices are mediated through the degree-3 vertices.

Therefore the greedy algorithm will devolve into something like a brute-force search through the size $2^{10000}$ space of valuations for the variables in the 3SAT problem.

-
That's an awesome answer, thank. – Cris Stringfellow Dec 27 '12 at 14:35
Excellent raping of the greedy algorithm. – Cris Stringfellow Dec 27 '12 at 14:44