论文标题
匹配有序和可分离的超图
Matching Orderable and Separable Hypergraphs
论文作者
论文摘要
超图中的完美匹配是一组划分顶点的边缘。我们研究了在有序和可分离的超图中确定完美匹配的复杂性。我们表明，可分开的超图类别中严格包含了有序的超图。因此，我们表明，对于每个固定的$ k $，确定可订购$ k $ - hypergraphs的完美匹配是多项式时间的，但是对于每个固定的$ k \ geq 3 $，对于可分离的超透明剂来说，它是NP的完整时间。
A perfect matching in a hypergraph is a set of edges that partition the set of vertices. We study the complexity of deciding the existence of a perfect matching in orderable and separable hypergraphs. We show that the class of orderable hypergraphs is strictly contained in the class of separable hypergraphs. Accordingly, we show that for each fixed $k$, deciding perfect matching for orderable $k$-hypergraphs is polynomial time doable, but for each fixed $k\geq 3$, it is NP-complete for separable hypergraphs.
