# Minimal edge cover of the hypergraph

We know that minimal edge cover for the normal graph is polynomial time solvable. Is it also true for hypergraph?

## 1 Answer

The polynomial algorithm for "classical" graph is based on a maximum matching algorithm completed with the isolated nodes. 3-dimensional matching is known to be NP-complete (https://en.wikipedia.org/wiki/3-dimensional_matching). This is a case of minimal edge cover for hypergraph. Thus the answer is no.

• My actual question is I have sets each of cardinality 3.I want to find set cover.How can I solve it? – Manoharsinh Rana Jan 31 at 12:08
• in a tripartite graph or not necessary ? – Vince Jan 31 at 12:42
• I am talking about this. en.wikipedia.org/wiki/Set_cover_problem only difference is that each set has exactly three element. What I am doing is that treat each set as an edge, each element as a vertex.That will create hypergraph.Now I want to find edge cover of this hypergraph. Is it polynomial time? – Manoharsinh Rana Jan 31 at 13:20
• No it is not polynomial, only cardinality 2 is. – Vince Jan 31 at 13:39
• is the maximal matching of hypergraph polynomial time solvable? – Manoharsinh Rana Jan 31 at 14:48