algorithm - 在二部图的一侧找到支配的顶点集

Question

我有一个像这里的二分图

我试图找到图右侧的最小节点集，使得图左侧的每个节点都恰好连接到图右侧的一个节点。对于上图，看起来像这样。

我不太确定我该怎么做。我有一种感觉，它类似于图论或基础 CS 中的一些常见问题，并且通过一些转换变得等同于具有已知解决方案的问题。

Answer 1

你的问题是 NP-hard，因为 set cover problem (或者更确切地说，大卫指出的 exact cover problem )可以简化为它。一种简单的指数时间算法适用于节点子集上的动态规划。它可以在时间 O(2^m * n) 内实现，其中 m 是左侧的节点数，n 是右侧的节点数。

基于 Branch & Bound 的算法在实践中可能更有效。