Finding Perfect Matchings in Dense Hypergraphs

We show that for any integers k ≥ 3 and c ≥ 0 there is a polynomial-time algorithm, that given any n-vertex k-uniform hypergraph H with minimum codegree at least n/k – c, finds either a perfect matching in H or a certificate that no perfect matching exists.