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?

Improve this question
$\endgroup$
2
  • $\begingroup$ You can think of it as bounded occurrence exact cover by 3-sets problem. $\endgroup$
    – Mohammad Al-Turkistany
    Nov 28, 2013 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, 2013 at 20:21

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

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

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