1
$\begingroup$

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!

$\endgroup$

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.