Is bipartite maximal matching an NP Hard or NP Complete or neither?

$\begingroup$

Is the bipartite maximal matching problem is NP hard or NP complete or neither? If it's either can someone cite a paper saying so? Also, if its not too trivial to ask, can someone explain NP Hard and NP Complete concepts too?

PS: It is a one- to - many matching

$\endgroup$

1 Answer

$\begingroup$

Bipartite maximal matchings can be found in time polynomial to the number of vertices and edges using the Hopcraft-Karp algorithm. So it is not an NP-complete problem unless P = NP.

The concepts of NP-hardness and NP-completeness are covered in the Computer Science StackExchange question "In basic terms, what is the definition of P, NP, NP-Complete, and NP-Hard?"

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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