# Bounded occurrence 3D matching problem

It is NP-hard to approximate maximum 3D matching problem even if each element occurs exactly in two triples. I'm interested in the following decision version of 3D matching.

Informally, Given a set of triples $F$ of elements such that each element occurs exactly in two triples, Is there a subset of $F$ such that each element occurs in exactly one triple?

Is this decision problem solvable in polynomial time? Is it $NP$-complete?

• You can think of it as bounded occurrence exact cover by 3-sets problem. Nov 28, 2013 at 20:36
• If you can view your problem as exact hitting set, then that would probably be helpful. The XSAT problem asks for a truth assignment such that exactly one literal in a clause is set to true. Monotone XSAT corresponds to exact hitting set. Many XSAT variants have been considered, and many are known to be NP-complete. You could skim through these slides. Of course, this is probably irrelevant if the problem can't be seen as exact hitting set :-)
– Juho
Dec 17, 2013 at 20:21