Jelly, 216 213 bytes
0ịT3ŀÐḟ3Ñ€
ñ4ñ3ñ1Ɗ_=1ʋƇñ1Ḣ$⁸;ⱮḢ;U$3ịḢ}⁺¦⁹$2¡Wʋ3¦ɼ$02ịñ3ß1Ẹ?Ʋ?ȯƊẸaŒḊ2ƑƲ¿Ẹ
ịị®$}
ç4ç3ç1=®ẈḢ¤ƊƇƊ,¹Ƈ$;ç1‘$Ṫ}Ḣ}¦;F¥¹¹4ƭ€ɼ
;@©;L‘$aL$Ɗ,¬ȧ"Tɗɗ/2ịḢÇ®0;3ŀ1$>/Ʋ?ƲẠ¿
ŒṪ§Ḃ$Ƈṭ+Ø.,UN;$¤fɗ¥€$’Uæ.L‘ṪṬȧ€Ɗ€S,@F0€$ȯ"\ṫ-Ç$Ñṛ®ƲÐL3ịTLH
A full program that takes a binary matrix and prints an integer. This generates a bipartite graph and then uses the Hopcroft-Karp method; it’s loosely based on the pseudo code on the Wikipedia page, but obviously has to stick within what’s possible in Jelly. I think it should meet the complexity requirement since the underlying method does, and manages to complete all challenges within abut 45 seconds total on TIO.