# Restriction of Exact Cover by 3-sets

Exact cover by 3-sets problem is defined as:

Instance: a set $X = \{ x_1,x_2,...,x_{3n}\}$ and a family $F = \{ ( x_{i_1}, x_{i_2}, x_{i_3}) \}$ of 3-elements subsets of $X$ (triples);
Question: Is there a subfamily $F'$ of $F$ such that every element in $X$ is contained in exactly one triple of $F'$.

It is known that Exact cover by 3-sets problem is NP-complete even if input is restricted such that each element of $X$ appears exactly in three triples.

Is still NP-complete if the input is restricted further such that no pair of input triples share more than one element of $X$?

I didn't check if the Bangye's solution is correct/simpler, but a quick transformation from RESTRICTED X3C (the name is the same used by Gonzales) to SINGLE OVERLAP RESTRICTED X3C (the name is invented) that should work is:

• Replace each subset $$C_j=\{x_1,x_2,x_3\}$$ adding 6 new elements $$z_{j,1},z_{j,2},...,z_{j,6}$$ and 5 new three elements subsets
$$L_{j,1}=\{x_1,z_{j,1},z_{j,4}\}$$,
$$L_{j,2}=\{x_2,z_{j,2},z_{j,5}\}$$,
$$L_{j,3}=\{x_3,z_{j,3},z_{j,6}\}$$,
$$L_{j,4}=\{z_{j,1},z_{j,2},z_{j,3}\}$$,
$$L_{j,5} = \{ z_{j,4},z_{j,5},z_{j,6}\}$$ .

like in the figure below (blue triples). Informally, the three elements originally in $$C_j$$ are grouped and in order to include elements $$z_{j,1},...,z_{j,6}$$ the exact cover must include the group of triples $$L_{j,1},L_{j,2},L_{j,3}$$ OR the two triples $$L_{j,4},L_{j,5}$$, but not both.

At this point no pair of triples share more than one element and each element is included in exactly 3 triples; except elements $$z_{j,1},...,z_{j,6}$$ which are included only in two triples.

• In order to fix this it's enough to add a duplicate of every element element $$x_i \rightarrow x'_i, z_i \rightarrow z'_i$$, a duplicate of each triple containing $$x_i$$ or $$z_i$$ elements using the corresponding duplicated elements (green triples in the figure below) and for each original triple $$C_j$$ add three new elements $$t_{j,1},t_{j,2},t_{j,3}$$ and 7 new dummy subsets with elements:
$$D_{j,1} =\{ z_{j,2},z_{j,6},t_{j,1} \}$$,
$$D_{j,2} =\{ z_{j,3},z_{j,4},t_{j,2} \}$$,
$$D_{j,3} =\{ z_{j,1},z_{j,5},t_{j,3} \}$$,
$$D_{j,4} =\{ z_{j,2}',z_{j,6}',t_{j,2} \}$$,
$$D_{j,5} =\{ z_{j,3}',z_{j,4}',t_{j,3} \}$$,
$$D_{j,6} =\{ z_{j,1}',z_{j,5}',t_{j,1} \}$$,
$$D_{j,7} =\{ t_{j,1},t_{j,2},t_{j,3} \}$$ (yellow triples in the figure below).

(note that the $$z,z'$$ elements of dummy triples $$D_{j,1}, D_{j,2}, ..., D_{j,6}$$ and elements $$t$$ of dummy triples $$D_{j,4},D_{j,5},D_{j,6}$$ are "shifted" to avoid triples that share more than one element)

($$\Rightarrow$$) Suppose that $$\bigcup_{j \in A \subseteq \{1,...,3n\}} C_j$$ is an exact cover of the original RESTRICTED X3C instance. Then by construction:

$$\bigcup_{j \in A } ( L_{j,1} \cup L_{j,2} \cup L_{j,3} \cup L'_{j,1} \cup L'_{j,2} \cup L'_{j,3} \cup D_{j,7} ) \cup \bigcup_{j \notin A } (L_{j,4} \cup L_{j,5} \cup L'_{j,4} \cup L'_{j,5} \cup D_{j,7})$$

is an exact cover of SINGLE OVERLAP RESTRICTED X3C.

($$\Leftarrow$$) Suppose that there exists an exact cover of the SINGLE OVERLAP RESTRICTED X3C instance. Every original element $$x_i$$ must be included exactly once in the cover, but, as seen above, the only way to include an element $$x_i$$ is by choosing a group of triples $$L_{j,1},L_{j,2},L_{j,3}$$ that correspond to an original triple $$C_j$$ that contains $$x_i$$. Furthermore if $$L_p, L_q, p \neq q$$ are included in the exact cover we have $$L_p \cap L_q = \emptyset$$. So the collection $$L_{j,k}$$ of subsets in the SINGLE OVERLAP RESTRICTED X3C exact cover correspond to a valid cover $$\bigcup C_j$$ of the original RESTRICTED X3C instance.

The reduction can be done in polynomial time, so we can conclude that SINGLE OVERLAP RESTRICTED X3C is NP-complete.

Just note that a SINGLE OVERLAP RESTRICTED X3C instance built using the above reduction can contain two valid and distinct exact covers of the original RESTRICTED X3C problem, but we are sure that if only one exact cover exists, it can be "mirrored" to form a valid exact cover of SINGLE OVERLAP RESTRICTED X3C.

Let me know if you need a more formal proof for a paper.

Update 20/04/2020: I noticed that the previous figure had a small issue in the dummy triples and I fixed it.

• Thanks Marzio, I will give you my feedback on your reduction. Jan 1 '14 at 13:26
• Thanks Marzio for your nice reduction. Are you aware of other NP-completeness proofs that rely heavily on redundant encoding? Jan 6 '14 at 11:25
• Thanks :). For redundant encoding, do you mean something like the "duplicated elements trick" above? Jan 6 '14 at 12:34
• @MohammadAl-Turkistany: P.S. I'm going to post it on my blog, too; my English is not so good, do you think that "SINGLE OVERLAP RX3C" is a good name? Or perhaps it's better "single overlapping RX3C" or "single share RX3C",...? Jan 6 '14 at 12:42
• Yes. I mean "duplicated elements trick". Regarding the name, I suggest Unique overlap restricted X3C problem. Jan 6 '14 at 19:05

I guess so. In the following paper, it was shown that the partition-into-triangle (PIT) problem with the restriction that no two triangles share a common edge is NPC. The reduction is simple. Just replace the subgraph in (Garey and Johnson, p 68) with the following subgraph. I guess that the restricted PIT problem can be reduced to your problem.

On the Maximum Locally Clustered Subgraph and Some Related Problems

• I don't have access to the paper. Can you provide a reduction? Dec 31 '13 at 20:27
• @MohammadAl-Turkistany, have you tried contacting the authors of the paper? Often authors are happy to share a copy of their paper with other researchers.
– D.W.
Dec 31 '13 at 23:04
• I am the author. The key point of the reduction is given in the answer. If you still need the paper, just email me. Jan 1 '14 at 3:52
• Thanks Bangye. Are you considering inputs with BOTH restrictions? In the input instance, each element of $X$ appears exactly in three triples AND no pair of input triples share more than one element of $X$. Jan 1 '14 at 8:23
• Thanks Bangye for your answer. I wish that I was able to accept both answers. Jan 6 '14 at 11:31