You may know a classic $\textsf{NP}$-complete problem known as X3C (exact cover by 3-sets). In this post, I’ll show that a restricted version of X3C (called RX3C) is also $\textsf{NP}$-complete.

I think it was first proven in Clustering to minimize the maximum intercluster distance by Teofilo F. Gonzalez (it’s often cited as such), but I see two problems with this paper:

  1. The proof is overcomplicated,
  2. The paper references Computers and Intractability by Garey and Johnson for an intermediate problem (between X3C and RX3C), in which they in turn refer to their own “unpublished results”.

Yeah, so I decided that it would be good to provide a proof of this result, so that one doesn’t need to go search for some “unpublished results” from 1979.

Problem statements#

The X3C problem is defined as follows. Given a set $U = \{u_1, u_2, \ldots, u_{3q}\}$ and a family $\mathcal{S} = \{S_1, S_2, \ldots, S_m\}$ of size-3 subsets of $U$, find if there is a subfamily $\mathcal{C} \subseteq \mathcal{S}$ such that every element of $U$ occurs in exactly one member of $\mathcal{C}$ (i.e., $\mathcal{C}$ exactly covers $U$).

RX3C introduces an additional restriction: each element $u \in U$ appears in exactly three subsets $S \in \mathcal{S}$.

For the sake of the proof, we will introduce yet another variant of X3C, which we will call X3C’. In this problem, every element $u \in U$ appears at most three times in $\mathcal{S}$.

X3C $\leq_p$ X3C'#

For now, we want to prove that X3C’ is at least as hard as X3C (the latter reduces polynomially to the former). To do that, we need to show that we can convert an instance of X3C (in which some $u \in U$ appears more than three times in $\mathcal{S}$) to X3C’. Let’s consider each such element $u$ separately.

We can replace $u$ in $\mathcal{S}$ with new elements: $u_1, u_2, \ldots, u_p$, each appearing exactly once. Now, it’s sufficient to add the following gadget to $\mathcal{S}$: $$ \{u_0, x_0, y_0\}, \quad \{\textcolor{Orange}{u_1}, x_0, y_0\} $$ $$ \{\textcolor{Orange}{u_1}, x_1, y_1\}, \quad \{\textcolor{Orange}{u_2}, x_1, y_1\} $$ $$ \{\textcolor{Orange}{u_2}, x_2, y_2\}, \quad \{\textcolor{Orange}{u_3}, x_2, y_2\} $$ $$ \cdots $$ $$ \{\textcolor{Orange}{u_p}, x_p, y_p\}, \quad \{u_{p+1}, x_p, y_p\} $$ Elements that we’ve added beforehand are marked in orange. Let’s denote 3-sets from the first columns as $A_0, \ldots, A_p$ and from the second one as $B_0, \ldots, B_p$. It’s important to note that when we choose $A_i$ as part of $\mathcal{C}$, we cannot choose $B_i$ and vice versa. Also, if we choose $B_i$, we cannot choose $A_{i+1}$ (because of $u_{i+1}$), so we need to choose $B_{i+1}$ (because of $x_{i+1}$ and $y_{i+1}$). By induction, once we choose $B_i$, we must also choose every $B_j$ for $j > i$.

We must start by choosing $A_0$ (because of $u_0$), so the only valid solution for this gadget is to choose sets $A_0, \ldots, A_{r-1}, B_r, \ldots, B_p$. That leaves exactly one element — $u_r$ — uncovered, thus we need to use a set from the original $\mathcal{S}$. This proves that a solution to this instance exists if and only if a solution to the original instance exists. Noting that now every element in $U$ appears at most three times in $\mathcal{S}$, we complete the reduction from X3C to X3C'.

X3C’ $\leq_p$ RX3C#

To reduce X3C’ to RX3C, we proceed as follows:

  1. While there is a $u \in U$ that appears exactly once in $\mathcal{S}$, remove $u$ from $U$, remove $S_i = \{u, x, y\} \in \mathcal{S}$ and every $S_j \in \mathcal{S}$ that contains $x$ or $y$. In this way, we effectively simulate adding $S_i$ to $\mathcal{C}$.

  2. If there is a $u \in U$ that does not appear in any $S_i \in \mathcal{S}$, the cover is surely impossible, so we can reduce it into a trivial no-instance.

After this process, every $u \in U$ appears exactly two or three times in $\mathcal{S}$. Note that the number of elements that appear exactly twice is divisible by 3.

  1. While there are three elements $u_1, u_2, u_3 \in U$ that appear twice in $\mathcal{S}$, we add a following gadget to $\mathcal{S}$: $$ \{\textcolor{orange}{u_1}, x, y\}, \{\textcolor{orange}{u_2}, x, z\}, \{\textcolor{orange}{u_3}, y, z\}, \{x, y, z\}. $$

In this way, the elements $u_1, u_2, u_3, x, y, z$ each appear exactly three times in $\mathcal{S}$, and — since we must choose $\{x, y, z\}$ (otherwise one of $x, y, z$ would remain uncovered) — this does not affect the existence of an exact cover.

At this point, we have an instance of RX3C, showing that the problem is $\textsf{NP}$-hard. Since it clearly belongs to $\textsf{NP}$, it is therefore $\textsf{NP}$-complete.

If you’d like, you can leave a comment on Bluesky.