Question

Consider a collection C of subsets of a nite set V . (V; C) is called a hypergraph. A hypergraph (V; C) is 3-regular if every subset in C contains exactly three elements. A subcollection M of C is matching if all subsets in M are disjoint. Show that there exists a polynomial-time 3-approximation for the maximum matching problem in 3-regular hypergraphs as follows: Given a 3-regular hypergraph, find a matching with maximum cardinality.

Answer 1

Explanation:

polynomial-time 3-approximation for the maximum matching problem in 3-regular hypergraphs as follows: Given a 3-regular hypergraph, find a matching with maximum cardinality.