graph - 具有互斥边的二部图中的完美匹配

问题

我想解决一些边互斥的二分图问题中的完美匹配问题 。

例子

左顶点：a，b，c

右顶点：x,y,z

边：(a,x), (a,y), (b,z), (c,y)

独占对：(b,z)和(c,y)

答：没有完美匹配

问题

是P还是NP的问题？

解决方案尝试

我知道二分图问题中的完美匹配在P中。但我找不到上述版本的这个问题的多项式时间算法。我也试过证明它是NP，但没有任何运气。

标签： graphtime-complexity

如果您的意思是边是“互斥的”，即它们不共享一个顶点，那么您描述的问题是二分图问题中一般完美匹配的一个子集。

还要尝试更具体地使用术语 P 和 NP。P 是 NP 的子集。因此 ，二分图问题中的完美匹配也在 NP 中，因为它在 P 中。不同的是，您可能的意思是NP-hardness。这基本上意味着“至少与 NP 中的每个问题一样难”。

因此，您的问题应该是：“问题在 P 中吗？”，因为如果我们有解决方案，我们可以轻松检查它，因此它在 NP 中。我们可以在多项式时间内检查它的性质实际上是NP的定义。

就像我说的，据我了解，您的问题只是问题的一个子集，因此在 P 中也是如此。