I have been thinking about this problem for a long time. If anyone can help me out here, I'd really appreciate it.

A hypergraph $H = (V,E)$ consists of a set $V = \{v_1, v_2, \cdots, v_n\}$ of vertices and a set $E = \{e_1, e_2, \cdots , e_m\}$ of edges, each being a subset of $V$.

A subset $M \subseteq E(H)$ is a matching if every pair of edges from $M$ has an empty intersection.

The dual $H^*$ of $H$ is a hypergraph whose vertices and edges are interchanged, so that the vertices are given by $\{e_1, e_2, \cdots , e_m\}$ and whose edges are given by $X = \{X_1, X_2, \cdots, X_n\}$ where $X_j = \{e_i | v_j \in e_i \}$, that is $X_j$ is the collection of all edges containing $v_j$.

The degree $d(v)$ of a vertex v is the number of edges that contain it. H is k-regular if every vertex has degree k.

The dual of a uniform hypergraph is regular and vice versa.

My question: maximum matching problem is equivalent to maximum independent set problem in its dual graph, right? We know that k-uniform maximum matching has k-approximation algorithm, then maximum independent set in its dual hypergraph also has k-approximation ?

If we reduce the dual hypergraph to general graph (k = 2) by replacing each edge with a clique (convert 1-vertex edge into 1 vertex), does this make the maximum independent vertex set in the resulted general graph k-approximation??

I have been thinking about this for a long time, but not sure about it. If you have any thought please help!


Your Answer

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

Browse other questions tagged or ask your own question.