10
$\begingroup$

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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
9
$\begingroup$

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,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

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

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thanks Marzio, I will give you my feedback on your reduction. $\endgroup$
    – Mohammad Al-Turkistany
    Jan 1, 2014 at 13:26
  • $\begingroup$ Thanks Marzio for your nice reduction. Are you aware of other NP-completeness proofs that rely heavily on redundant encoding? $\endgroup$
    – Mohammad Al-Turkistany
    Jan 6, 2014 at 11:25
  • $\begingroup$ Thanks :). For redundant encoding, do you mean something like the "duplicated elements trick" above? $\endgroup$
    – Marzio De Biasi
    Jan 6, 2014 at 12:34
  • $\begingroup$ @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",...? $\endgroup$
    – Marzio De Biasi
    Jan 6, 2014 at 12:42
  • $\begingroup$ Yes. I mean "duplicated elements trick". Regarding the name, I suggest Unique overlap restricted X3C problem. $\endgroup$
    – Mohammad Al-Turkistany
    Jan 6, 2014 at 19:05
7
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\begingroup$ I don't have access to the paper. Can you provide a reduction? $\endgroup$
    – Mohammad Al-Turkistany
    Dec 31, 2013 at 20:27
  • $\begingroup$ @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. $\endgroup$
    – D.W.
    Dec 31, 2013 at 23:04
  • 1
    $\begingroup$ I am the author. The key point of the reduction is given in the answer. If you still need the paper, just email me. $\endgroup$
    – Bangye
    Jan 1, 2014 at 3:52
  • $\begingroup$ 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$. $\endgroup$
    – Mohammad Al-Turkistany
    Jan 1, 2014 at 8:23
  • $\begingroup$ Thanks Bangye for your answer. I wish that I was able to accept both answers. $\endgroup$
    – Mohammad Al-Turkistany
    Jan 6, 2014 at 11:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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