NPC Pill #1: Single Overlap RX3C

NPC Pills (NP-Complete pills) is a collection of some NP-completeness proofs that I posted on the Q&A sites and Up to my knowledge they are original and some of them are not so trivial. At present, most of them are just sketches that contain the NP-hardness reduction idea, but for some of them I wrote (or I’m going to write) a more formal paper. If you are particularly interested in one of them write me an email.


The EXACT COVER BY 3-SETS (X3C) problem is:

Instance: Set $X = \{x_1,x_2,…,x_{3q}\}$ and a collection $C = \{C_1,…,C_m\}$ of 3-element subsets of $X$.
Question: Does $C$ contain an exact cover for $X$, i.e. a subcollection $C’ \subseteq C$ such that every element of $X$ occurs in exactly one member of $C’$?

X3C is NP-complete [1], and as shown in [2] it remains NP-complete even if every element $x_i$ contained in exactly 3 subsets of $C$ (Restricted Exact Cover by 3-Sets – RX3C).

We proved that it remains NP-complete even if every pair of subsets in $C$  share at most one element; i.e. for all $i \neq j,\; | C_i \cap C_j | \leq 1$ and we call this restricted version SINGLE OVERLAP RX3C.

[1] M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7.
[2] Teofilo F. Gonzalez: Clustering to Minimize the Maximum Intercluster Distance. Theor. Comput. Sci. 38: 293-306 (1985).


One thought on “NPC Pill #1: Single Overlap RX3C

  1. hi MdB nice work on all this, must say though liked your older blog name “fractalmuse” a bit more than “nearly 42″… is that a douglas adams reference? the blog is neat & esp like the ref to the computational complexity of video games, think have seen 1-2 of your answers on relating to that… have you ever heard of kozas work on GA/GPs applied to video games? you might enjoy it. [havent found a really good ref on subj by him though]…. hey maybe drop by chat sometimes more than 1/yr wink… ps wordpress has some nice features [eg latex etc, although looks like youve got that worked out], you might consider it for your blog, will follow your blog for 1 if you ever go that route….

Leave a Reply

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