NPC Pills (NP-Complete pills) is a collection of some NP-completeness proofs that I posted on the Q&A sites cstheory.stackexchange.com and cs.stackexchange.com. 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.

NPC Pill #3: Pick 3 or Pick 2 … another NP-complete 3DM variant

The following variant of the 3-Dimensional Matching problem (3DM) was posted on cstheory.stackexchange.com, a question and answer site for professional researchers in theoretical computer science and related fields:

Definition. 3-DIMENSIONAL MATCHING VARIANT
Input: Set $M \subseteq X \times Y \times Z$ where $X,Y,Z$ are disjoint sets; we call $M_{XY}= \{(x,y)\mid \exists z \text{ s.t. } (x,y,z)\in M \}$ the set of pairs of $X \times Y$ that appear in the triples of $M$, and $M_{XZ}= \{(x,z)\mid \exists y \text{ s.t. } (x,y,z)\in M \}$ the set of pairs of $X \times Z$ that appear in the triples of M.
Question: Does there exist a set $M’ \subseteq M \cup M_{XY} \cup M_{XZ} $ such that every element of $X \cup Y \cup Z$ is included in a triple or a pair of $M’$ exactly once?

Informally we want to build an exact cover of $X \cup Y \cup Z$ using the triples of $M$ or one of the two pairs $(x,y), (x,z)$ that are contained in a triple $(x,y,z) \in M$.

The problem is NP-complete, click the following link to download the technical report with the reduction (we also discuss some other variants of the problem).

Click here to download the technical report

If you have some comments or find some errors, contact me via email.