我一直在试图找出一个多项式时间算法来解决这个问题,但没有成功。我对NP完全不熟悉只是想知道这个问题是否真的是NP完全问题,我不应该浪费任何进一步的努力,试图提出一个多项式时间算法。
这个问题很容易描述和理解给定abipartite graph,您必须从一个顶点集(例如a)中选择的最小顶点数是多少,以便B中的每个顶点与至少一个选定顶点相邻。

最佳答案

不幸的是,这是NP-hard;从Set Cover可以很容易地减少(事实上,可以说这只是表达同一问题的不同方式)在集合覆盖中,我们得到了一个接地集f,一个f子集的集合c,和一个数字k,我们想知道我们是否可以通过选择c中最多k个集合来覆盖f的所有n个接地集元素。为了减少这个问题:在b中为每个接地元素创建一个顶点,在a中为c中的每个集合创建一个顶点,当地面元素v在集合u中时,添加一个边uv。如果有某种算法可以有效地解决您描述的问题,它可以解决我刚才描述的实例,这将立即给出原始集合覆盖问题的解决方案(这是NP难的)。
有趣的是,如果我们被允许从整个图中选择顶点(而不是仅仅从A),则由于二元最大匹配算法,该问题在多项式时间内是可解的,这是由于Kőnig's Theorem

10-06 05:40
查看更多