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
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?"