<p>I think the problem of hyperedge coloring of a 3-regular 3-uniform hypergraph (with 3 colors) is reducible to this problem and vice versa, where the set X is corresponds to the vertex set V and each member of the set F is corresponds to a hyperedge. Then, it is as hard as that problem.</p>

CC BY-SA 4.0
2022-06-17T07:59:56.453Z
2022-06-17T07:59:56.453Z
Majid Zohrehbandian
<p>In the Exact Cover by 3-Sets problem, we are given a set <span class="math-container">$X = \{x_1, x_2,\ldots, x_{3n}\}$</span> and a family of subsets <span class="math-container">$F = \{\{x_{i_1}, x_{i_2}, x_{i_3}\}\}$</span> of 3-element subsets of <span class="math-container">$X$</span>.
The question is then whether there exists a family of subsets <span class="math-container">$F'\subseteq F$</span> that forms an exact cover of <span class="math-container">$X$</span>.</p>
<p>It is known that the problem remains NP-hard under some restrictions, e.g., to instances in which each element appears in exactly three subsets and <span class="math-container">$\lvert F_i\cap F_j\rvert\leq 1$</span> for all <span class="math-container">$F_i, F_j\in F$</span>. (See <a href="https://cstheory.stackexchange.com/questions/20386/restriction-of-exact-cover-by-3-sets">this</a> answer and its referenced paper.)</p>
<p>I would like to modify the problem in a slightly different way: the only restriction on the input is that we know that each element appears in exactly three subsets. The question, however, is this: can the family <span class="math-container">$F$</span> be partitioned into three disjoint families <span class="math-container">$F_1, F_2, F_3$</span> such that each <span class="math-container">$F_i$</span> is an exact cover?</p>
<p>Is this problem already known to be NP-hard/polynomial-time solvable? Another way to view it would be to consider a graph with vertices corresponding to subsets and edges being added if the respective subsets have a non-empty intersection. The problem then asks whether the graph is 3-colorable. Has 3-coloring (or k-coloring) perhaps been studied on this class of set-intersection graphs?</p>

CC BY-SA 4.0
2022-06-13T16:29:03.857Z
https://cs.stackexchange.com/q/152290/755
D.W.
<cc.complexity-theory><np-hardness><np-complete><exact-cover>
Exact Cover by 3-Sets variation: Partition Into Exact Covers by 3-Sets
NayCey
# Exact Cover by 3-Sets variation: Partition Into Exact Covers by 3-Sets

(Asked by: username_0 on 2022-06-13)

In the Exact Cover by 3-Sets problem, we are given a set $X = \{x\_1, x\_2,\ldots, x\_{3n}\}$ and a family of subsets $F = \{\{x\_{i\_1}, x\_{i\_2}, x\_{i\_3}\}\}$ of 3-element subsets of $X$.
The question is then whether there exists a family of subsets $F'\subseteq F$ that forms an exact cover of $X$.

It is known that the problem remains NP-hard under some restrictions, e.g., to instances in which each element appears in exactly three subsets and $\lvert F\_i\cap F\_j\rvert\leq 1$ for all $F\_i, F\_j\in F$. (See [this](https://cstheory.stackexchange.com/questions/20386/restriction-of-exact-cover-by-3-sets) answer and its referenced paper.)

I would like to modify the problem in a slightly different way: the only restriction on the input is that we know that each element appears in exactly three subsets. The question, however, is this: can the family $F$ be partitioned into three disjoint families $F\_1, F\_2, F\_3$ such that each $F\_i$ is an exact cover?

Is this problem already known to be NP-hard/polynomial-time solvable? Another way to view it would be to consider a graph with vertices corresponding to subsets and edges being added if the respective subsets have a non-empty intersection. The problem then asks whether the graph is 3-colorable. Has 3-coloring (or k-coloring) perhaps been studied on this class of set-intersection graphs?

**Tags:** cc.complexity-theory, np-hardness, np-complete, exact-cover

> **Comments:**
> **username_1**: https://cs.stackexchange.com/q/152290/755  

---

## 1 answers

### Answer by username_2 on 2022-06-17. Score: 1

I think the problem of hyperedge coloring of a 3-regular 3-uniform hypergraph (with 3 colors) is reducible to this problem and vice versa, where the set X is corresponds to the vertex set V and each member of the set F is corresponds to a hyperedge. Then, it is as hard as that problem.


---

