3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You can think of it as bounded occurrence exact cover by 3-sets problem. $\endgroup$ – Mohammad Al-Turkistany Nov 28 '13 at 20:36
  • $\begingroup$ 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 :-) $\endgroup$ – Juho Dec 17 '13 at 20:21
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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