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


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.

  • $\begingroup$ My actual question is I have sets each of cardinality 3.I want to find set cover.How can I solve it? $\endgroup$ – Manoharsinh Rana Jan 31 at 12:08
  • $\begingroup$ in a tripartite graph or not necessary ? $\endgroup$ – Vince Jan 31 at 12:42
  • $\begingroup$ 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? $\endgroup$ – Manoharsinh Rana Jan 31 at 13:20
  • $\begingroup$ No it is not polynomial, only cardinality 2 is. $\endgroup$ – Vince Jan 31 at 13:39
  • $\begingroup$ is the maximal matching of hypergraph polynomial time solvable? $\endgroup$ – Manoharsinh Rana Jan 31 at 14:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.