patternMinor
Bounded occurrence 3D matching problem
Viewed 0 times
boundedproblemmatchingoccurrence
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#18455, answer score: 3
Revisions (0)
No revisions yet.