2
$\begingroup$

I have been so confused for a while!! Please help me with this, thank you very much in advance!!

Given 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$ is a matching if every pair of edges from $M$ has an empty intersection.

k-uniform hypergraph is a hypergraph with edges of size k.

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 \}$, which means $X_J$ is the collection of all edges that containing $v_j$.

My question: The below three statements are contradict. If (1) Maximum matching problem has no constant approximation, (2) minimum vertex cover has k-approximation, and (3) maximum matching and minimum vertex cover are bounded by each other, why one has no constant approximation while the other has???

  1. Maximum matching problem (is equivalent to maximum independent set problem in dual hypergraph) is NP-hard and cannot be approximated to a constant fact unless P = NP. https://en.wikipedia.org/wiki/Independent_set_(graph_theory)#Approximation_algorithms

  2. Minimum vertex cover in k-uniform hypergraph is k-approximation
    https://pdfs.semanticscholar.org/ac41/1c620fed0d6a620e2dd007f4dca9e27e2e95.pdf

  3. The cardinality of maximum matching set $\le$ cardinality of minimum vertex cover $\le k* $ cardinality of maximum matching set .

PROOF: According to the Duality theorem, cardinality of maximum matching set $\le$ cardinality of minimum vertex cover number.

In addition, in k-uniform hypergraph, consider a maximal matching set $I$ of $H$. Let $X$ be the set of vertices contained in the edges of $H$ and $\tau$ be the cardinality of maximum matching set. Because every edge has size $k$, the size of set $X$ is at most $k \cdot \tau$, otherwise, those edges are not independent.

Because $X$ is the set of all vertices in this hypergraph, $X$ intersects with every edge which means $X$ is a vertex cover.

Therefore, the cardinality of minimum vertex cover $\le$ cardinality of $X \le k \cdot \tau$.

Hence the cardinality of maximum matching set $\le$ cardinality of minimum vertex cover $\le k* $ cardinality of maximum matching set.

$\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.