algorithm - 完全断开二分图

Question

我有一个断开连接的二分无向图。我想完全断开图形。我可以执行的唯一操作是删除一个节点。移除一个节点会自动删除它的边。任务是最小化要删除的节点数。图中的每个节点最多有 4 条边。

通过完全断开图，我的意思是任何两个节点都不应通过链接连接。基本上是一个空边集。

Answer 1

我认为，你不能证明你的算法是最优的，因为事实上它不是最优的。

要完全断开你的图，最大限度地减少要删除的节点数，你必须删除属于你的图的最小顶点覆盖的所有节点。搜索最小顶点覆盖通常是 NP 完全的，但对于二部图，存在多项式时间解决方案。

在图中找到最大匹配(可能使用 Hopcroft–Karp algorithm )。然后使用 König's theorem获得最小的顶点覆盖:

Consider a bipartite graph where the vertices are partitioned into left (L) and right (R) sets. Suppose there is a maximum matching which partitions the edges into those used in the matching (E_m) and those not (E_0). Let T consist of all unmatched vertices from L, as well as all vertices reachable from those by going left-to-right along edges from E_0 and right-to-left along edges from E_m. This essentially means that for each unmatched vertex in L, we add into T all vertices that occur in a path alternating between edges from E_0 and E_m.

Then (L \ T) OR (R AND T) is a minimum vertex cover.