# 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. – Mohammad Al-Turkistany Nov 28 '13 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 '13 at 20:21

## 1 Answer

It is solvable in polynomial time.

Convert an instance of Bounded Occurrence 3DM to a cubic graph.

For each triple, create a vertex

For each element, there are exactly two triple containing it. So, there are exactly two vertices corresponding to these two triples. Connect these two vertices by an edge.

Now, a solution to your problem is an independent vertex cover.

A graph has an independent vertex cover iff. it is bipartite. Checking for bipartiteness can be done in polynomial time.