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$ in a tripartite graph or not necessary ? $\endgroup$ – Optidad Jan 31 '19 at 12:42
  • $\begingroup$ No it is not polynomial, only cardinality 2 is. $\endgroup$ – Optidad Jan 31 '19 at 13:39
  • $\begingroup$ Come on... Just read my answer... $\endgroup$ – Optidad Jan 31 '19 at 15:16
  • $\begingroup$ Well basically you were not talking about sets. It is the same yes. You can consider the set cover problem which is NP-complete to prove it. $\endgroup$ – Optidad Jan 31 '19 at 15:51
  • $\begingroup$ No this is not ! You never ask the same question since the begining of this conversation... Asking if a problem can be solved in polynomial time is absolutely not the same than asking "how to solve it ?" Over that, why do you ever talk of hypergraph if you do not care about.. ? I will not answer again here. You definitly have to write ONE proper question with all statements. $\endgroup$ – Optidad Jan 31 '19 at 16:09

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.