.png){kind=icon}
.png){kind=icon}
Return
Finding Matchings in Dense Hypergraphs
.png){kind=icon}
PRE
AI
DOI：10.1145/3768574.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Perfect matching
Fixed-parameter tractable algorithm
Journal
A
IF:
1.4
Papers:
43
Citations:
1.1K