Polynomial-time perfect matchings in dense hypergraphs
Polynomial-time perfect matchings in dense hypergraphs
复制标题
稠密超图中的多项式时间完美匹配
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Richard Mycroft
中科院分区：
文献类型：
--
作者：
Peter Keevash;Fiachra Knox;Richard Mycroft
设H是一个n阶k-图，对某个固定的c > 0，其最小余度至少为n/k + cn.在本文中，我们构造了一个多项式时间算法，找到一个完美的匹配H或证书，不存在。这基本上解决了Karpinski，Rucinski和Szymanska的问题，他们以前证明了这个问题对于最小余度n/k-cn是NP-难的。我们的算法依赖于一个理论结果的独立利益，在其中，我们将任何这样的超图没有完美的匹配使用一个家庭的基于格的建设。
Let H be a k-graph on n vertices, with minimum codegree at least n/k + cn for some fixed c > 0. In this paper we construct a polynomial-time algorithm which finds either a perfect matching in H or a certificate that none exists. This essentially solves a problem of Karpinski, Rucinski and Szymanska, who previously showed that this problem is NP-hard for a minimum codegree of n/k - cn. Our algorithm relies on a theoretical result of independent interest, in which we characterise any such hypergraph with no perfect matching using a family of lattice-based constructions.
影响因子：
1.1
作者：
D. Kühn;Deryk Osthus
通讯作者：
D. Kühn;Deryk Osthus