<p>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 <strong>SINGLE OVERLAP RESTRICTED X3C</strong> (the name is invented) that should work is:</p>

<ul>
<li><strong>Replace</strong> each subset <span class="math-container">$C_j=\{x_1,x_2,x_3\}$</span> adding 6 new elements <span class="math-container">$z_{j,1},z_{j,2},...,z_{j,6}$</span> and 5 new three elements subsets<br> <span class="math-container">$L_{j,1}=\{x_1,z_{j,1},z_{j,4}\}$</span>,<br><span class="math-container">$L_{j,2}=\{x_2,z_{j,2},z_{j,5}\}$</span>,<br><span class="math-container">$L_{j,3}=\{x_3,z_{j,3},z_{j,6}\}$</span>,<br><span class="math-container">$L_{j,4}=\{z_{j,1},z_{j,2},z_{j,3}\}$</span>,<br><span class="math-container">$L_{j,5} = \{ z_{j,4},z_{j,5},z_{j,6}\}$</span> .</li>
</ul>

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

<p><img src="https://i.sstatic.net/xXABo.jpg" alt="enter image description here"></p>

<p>At this point no pair of triples share more than one element and each element is included in exactly 3 triples; except elements <span class="math-container">$z_{j,1},...,z_{j,6}$</span> which are included only in two triples.</p>

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

<p>(note that the <span class="math-container">$z,z'$</span> elements of dummy triples <span class="math-container">$D_{j,1}, D_{j,2}, ..., D_{j,6}$</span> and elements <span class="math-container">$t$</span> of dummy triples <span class="math-container">$D_{j,4},D_{j,5},D_{j,6}$</span> are "shifted"  to avoid triples that share more than one element)</p>

<p><img src="https://i.sstatic.net/GX2fM.png" alt="enter image description here"></p>

<p>(<span class="math-container">$\Rightarrow$</span>) Suppose that <span class="math-container">$\bigcup_{j \in A \subseteq \{1,...,3n\}} C_j$</span> is an exact cover of the original RESTRICTED X3C instance. 
Then by construction:</p>

<p><span class="math-container">$$\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}) $$</span></p>

<p>is an exact cover of SINGLE OVERLAP RESTRICTED X3C.</p>

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

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

<p>Just note that a SINGLE OVERLAP RESTRICTED X3C instance built using the above reduction can contain two valid and <em>distinct</em> 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.</p>

<p>Let me know if you need a more formal proof for a paper.</p>

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

CC BY-SA 3.0
2014-01-01T13:26:38.597Z
Thanks Marzio, I will give you my feedback on your reduction.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-01-06T11:25:22.717Z
Thanks Marzio for your nice reduction. Are you aware of other NP-completeness proofs that rely heavily on redundant encoding?
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-01-06T12:34:37.567Z
Thanks :). For redundant encoding, do you mean something like the "duplicated elements trick" above?
Marzio De Biasi
CC BY-SA 3.0
2014-01-06T12:42:46.570Z
@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",...?
Marzio De Biasi
CC BY-SA 3.0
2014-01-06T19:05:24.343Z
Yes. I mean "duplicated elements trick". Regarding the name, I suggest Unique overlap restricted X3C problem.
Mohammad Al-Turkistany
CC BY-SA 4.0
2020-04-20T00:26:00.173Z
Wait, how is x3c np complete when restricted to sets of only three elements when I can use length(x)/3 combinations of C to check if one of them is an exact cover. That would mean that when X = 300. I would be doing combinations that don't exceed the bitlength of x. Maybe, I'm confused.
The T
CC BY-SA 4.0
2020-04-20T07:26:48.643Z
@TravisWells: see https://npcomplete.owu.edu/2014/06/10/exact-cover-by-3-sets/ Let me know if something is not clear
Marzio De Biasi
CC BY-SA 4.0
2013-12-31T19:24:57.070Z
2020-04-20T08:10:38.290Z
2020-04-20T08:10:38.290Z
Marzio De Biasi
<p>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.</p>

<p><a href="http://link.springer.com/chapter/10.1007/978-3-642-22616-8_19" rel="noreferrer">On the Maximum Locally Clustered Subgraph and Some Related Problems</a></p>

<p><img src="https://i.sstatic.net/2J1rG.jpg" alt="enter image description here"></p>

CC BY-SA 3.0
2013-12-31T20:27:56.080Z
I don't have access to the paper. Can you provide a reduction?
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-12-31T23:04:15.680Z
@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.
CC BY-SA 3.0
2014-01-01T03:52:57.130Z
I am the author. The key point of the reduction is given in the answer. If you still need the paper, just email me.
Bangye
CC BY-SA 3.0
2014-01-01T08:23:05.980Z
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$.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-01-06T11:31:13.350Z
Thanks Bangye for your answer. I wish that I was able to accept both answers.
Mohammad Al-Turkistany
CC BY-SA 4.0
2020-04-20T22:06:00.173Z
Hi, for the benefit of readers who would be interested in accessing your paper mentioned in the answer, could you deposit a copy of the paper in an open-access repository such as Zenodo or arXiv? If you are the author, this is probably allowed by the publisher, and would be useful to all of us that are not subscribed to Springer.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2013-12-31T14:05:20.933Z
2014-01-01T11:14:21.923Z
2014-01-01T11:14:21.923Z
Bangye
<p>Exact cover by 3-sets problem is defined as:</p>

<blockquote>
<b>Instance</b>: 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);<br>
<b>Question</b>: Is there a subfamily $F'$ of $F$ such that every element in $X$ is contained in exactly one triple of $F'$.
</blockquote>

<p>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 <a href="https://www.sciencedirect.com/science/article/pii/0304397585902245" rel="nofollow noreferrer">exactly in three triples</a>.</p>

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

<cc.complexity-theory>
Restriction of Exact Cover by 3-sets
Mohammad Al-Turkistany
# Restriction of Exact Cover by 3-sets

(Asked by: username_0 on 2013-12-31)

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](https://www.sciencedirect.com/science/article/pii/0304397585902245).

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

**Tags:** cc.complexity-theory


---

## 2 answers

### Answer by username_1 on 2013-12-31. Score: 9 | Accepted answer

I didn't check if the username_3'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.

![enter image description here](https://i.sstatic.net/xXABo.jpg)

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)

![enter image description here](https://i.sstatic.net/GX2fM.png)

($\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.

> **Comments:**
> **username_0**: Thanks Marzio, I will give you my feedback on your reduction.  
> **username_0**: Thanks Marzio for your nice reduction. Are you aware of other NP-completeness proofs that rely heavily on redundant encoding?  
> **username_1**: Thanks :). For redundant encoding, do you mean something like the "duplicated elements trick" above?  
> **username_1**: @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",...?  
> **username_0**: Yes. I mean "duplicated elements trick". Regarding the name, I suggest Unique overlap restricted X3C problem.  
> **username_2**: Wait, how is x3c np complete when restricted to sets of only three elements when I can use length(x)/3 combinations of C to check if one of them is an exact cover. That would mean that when X = 300. I would be doing combinations that don't exceed the bitlength of x. Maybe, I'm confused.  
> **username_1**: @TravisWells: see https://npcomplete.owu.edu/2014/06/10/exact-cover-by-3-sets/ Let me know if something is not clear  

---

### Answer by username_3 on 2013-12-31. Score: 7

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](http://link.springer.com/chapter/10.1007/978-3-642-22616-8_19)

![enter image description here](https://i.sstatic.net/2J1rG.jpg)

> **Comments:**
> **username_0**: I don't have access to the paper. Can you provide a reduction?  
> **username_4**: @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.  
> **username_3**: I am the author. The key point of the reduction is given in the answer. If you still need the paper, just email me.  
> **username_0**: Thanks username_3. 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$.  
> **username_0**: Thanks username_3 for your answer. I wish that I was able to accept both answers.  
> **username_5**: Hi, for the benefit of readers who would be interested in accessing your paper mentioned in the answer, could you deposit a copy of the paper in an open-access repository such as Zenodo or arXiv? If you are the author, this is probably allowed by the publisher, and would be useful to all of us that are not subscribed to Springer.  

---

