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$?

up vote 5 down vote accepted

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.

enter image description here

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,1},z_{j,4},t_{j,1}\}$,
    $D_{j,2} =\{z_{j,2},z_{j,5},t_{j,2}\}$,
    $D_{j,3} =\{z_{j,3},z_{j,6},t_{j,3}\}$,
    $D_{j,4} =\{z'_{j,1},z'_{j,4},t_{j,1}\}$,
    $D_{j,5} =\{z'_{j,2},z'_{j,5},t_{j,2}\}$,
    $D_{j,6} =\{z'_{j,3},z'_{j,6},t_{j,3}\}$,
    $D_{j,7} =\{t_{j,1},t_{j,2},t_{j,3}\}$ (yellow triples in the figure below).

enter image description here

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

  • Thanks Marzio, I will give you my feedback on your reduction. – Mohammad Al-Turkistany 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? – Mohammad Al-Turkistany Jan 6 '14 at 11:25
  • Thanks :). For redundant encoding, do you mean something like the "duplicated elements trick" above? – Marzio De Biasi 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",...? – Marzio De Biasi Jan 6 '14 at 12:42
  • Yes. I mean "duplicated elements trick". Regarding the name, I suggest Unique overlap restricted X3C problem. – Mohammad Al-Turkistany 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

enter image description here

  • I don't have access to the paper. Can you provide a reduction? – Mohammad Al-Turkistany 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
  • 1
    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 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$. – Mohammad Al-Turkistany Jan 1 '14 at 8:23
  • Thanks Bangye for your answer. I wish that I was able to accept both answers. – Mohammad Al-Turkistany Jan 6 '14 at 11:31

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.