algorithm - 用 1 种颜色对图表进行部分着色

Question

我刚刚开始阅读图论，并且正在阅读有关图着色的内容。我的脑海中浮现出这个问题:

我们必须仅使用一种颜色为无向图(不完全)着色，以便使着色节点的数量最大化。我们需要找到这个最大数量。我能够制定一种非循环图的方法:

我的方法:首先，我们将图划分为独立的组件，并对每个组件执行此操作。我们创建一个 dfs 树，并在遍历它时创建 2 个 dp 数组，以便根位于最后:

dp[0][u]=sum(dp[1][访问过的 child ])

dp[1][u]=sum(dp[0][访问过的 child ])

ans=max(dp[1][root],dp[0][root])

dp[0][i] 、 dp[1][i] 分别初始化为 0,1。

这里0表示无色，1表示有色。

但这不适用于循环图，因为我假设没有连接到访问过的子项。

有人可以指导我如何解决循环图的这个问题(而不是通过暴力)的正确方向吗？是否可以修改我的方法或者我们是否需要提出不同的方法？像为具有最少边缘的节点着色这样的贪婪方法会起作用吗？

Answer 1

这个问题也是 NP-Hard，被称为 maximum independent set problem .

一套S<=V如果对于每两个顶点 u,v ，则称其为图中的独立集在S ，没有边缘(u,v) .

最大尺寸S (这是您正在寻找的数字)称为图的独立数，不幸的是发现它是NP-Hard。

因此，除非 P=NP，否则您的算法对于通用图表将失败。

---

证明它相当简单，只要给定一个图 G=(V,E) ，创建互补图G'=(V,E')哪里(u,v)位于E'当且仅当(u,v)不在 E 中.

现在，给定一个图 G ，有一个大小为 k 的派系当且仅当存在一组独立的大小k在G' ，使用相同的顶点(因为如果 (u,v) 是独立集的两个顶点，则 (u,v) 中没有边 E' ，并且根据定义 E 中有一条边。对独立集，并且您在 G 中有一个派系。

自 clique problem是 NP-Hard，这使得这个也是如此。