1
$\begingroup$

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

$\endgroup$
1

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

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

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