16
$\begingroup$

What is the following variation on set cover known as?

Given a set S, a collection C of subsets of S and a positive integer K, do there exist K sets in C such that every pair of elements of S lies in one of the selected subsets.

Note: It is not hard to see that this problem is NP-Complete: Given a normal set cover problem (S, C, K), make three copies of S, say S', S'', and S''', then create your subsets as S''', |S| subsets of the form {a'} U {x in S'' | x != a} U {a'''}, |S| subsets of the form {a''} U {x in S' | x != a} U {a'''}, {a', a'' | a in C_i}. Then we can solve the set cover problem with K subsets iff we can solve the pair cover problem with K + 1 + 2 |S| subsets.

This generalizes to triples, etc. I would like to be able to not waste half a page proving this, and it is probably not obvious enough to dismiss as trivial. It is certainly sufficiently useful that someone has proved it, but I have no idea who or where.

Also, is there a good place to look for NP-Completeness results that are not in Garey and Johnson?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

To answer your second question, the Kahn-Crescenzi compendium of NP-hardness results is a valuable source for hardness results, and also covers many variants of core G&J problems. The entry for set cover is a good example of this.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ I had seen that before, and yes, it helps, but it does not even begin to scratch the surface of what has been proven NP-Complete. To give another example it took me much longer to find Uehara's proof that Vertex Cover was NP-complete on a 3 connected cubic planar graph than it took me to prove it. (Her proof was much cleaner than mine.) $\endgroup$
    – deinst
    Commented Aug 16, 2010 at 23:28
7
$\begingroup$

It sounds like you're generalizing set cover to consider not just elements of S, but every size-M subset of S. We can state the problem more generally:

"Given a set S, a collection C of subsets of S and a positive integer m, what is the smallest number of elements of C such that each size-M subset of S lies in one of the selected elements of C?"

This actually strikes me as being a fairly obvious generalization of set cover, and not one you'd need to spend time proving NP-complete beyond a single line. After all, choosing m=1 recovers the original set cover problem. Perhaps this more general formulation is good enough for your purposes to avoid needing to go into the details?

Your question about an updated set of NP-completeness results is a good one, and deserves its own question. Crescenzi and Kann have put together a useful compendium online here.

Second, it's hardly pervasive, but the Algorithms Design Manual by Steven Skiena is often a useful first stop for a large number of problems, and is available online in part.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I am interested only in m = 2. It may be that there is a one line proof, but said proof escapes me. I believe I stated that clearly in the second sentence of the question. $\endgroup$
    – deinst
    Commented Aug 16, 2010 at 23:19
  • $\begingroup$ Apologies; I didn't mean to suggest that there's a short proof in the pairwise case! The one-line proof I suggested is only in the general version of the problem: "the special case of m=1 recovers standard set cover". As you point out, the proof in the pairwise case is obvious (introduce dummy elements and sets to standard set cover to generate paired set cover), but yes, it would take a few lines to show it to be formal. I'll see if I can find any references to it in the literature. $\endgroup$
    – Anand Kulkarni
    Commented Aug 17, 2010 at 3:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.