2022/10/23 by Jie Han, Peter Keevash, Han, Jie +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2210.12643
openalex publication_date 2022/10/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the algorithmic decision problem that takes as input an n-vertex k-uniform hypergraph H with minimum codegree at least m-c and decides whether it has a matching of size m. We show that this decision problem is fixed parameter tractable with respect to c. Furthermore, our algorithm not only decides the problem, but actually either finds a matching of size m or a certificate that no such matching exists. In particular, when m=n/k and c=O(log n), this gives 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.