问题标签 [independent-set]

如您所知，找到最大独立集是 NP。是否有一种算法可以确定给定图是否具有至少 k 个顶点的独立集？请注意，我们不想找到它。我们只是想知道这样的事情是否存在。

除了在所有可能的独立集合中找到最大值的蛮力方法之外，我不相信存在一种算法可以在二分图中找到最大独立顶点集。

我想知道找到所有可能的顶点集的伪代码。

假设给定一个具有 4 个蓝色顶点和 4 个红色顶点的二分图。目前我会

我知道这种方式根本不会给我所有可能的独立集组合，因为在第一步之后，我选择了所有不匹配的下一个颜色顶点，而不是逐步完成所有可能。

例如给定一个匹配的图

有没有办法改进这个算法以更好地搜索所有可能性。我知道|二部图的最大集| = |红色| + |蓝色| - |最大匹配|。

问题出现的可能性是，在第一次选择所有可能的红色以获得给定的蓝色时，如果这些红色连接到所有其他可能的蓝色，那么我的集合只有所有 1 个蓝色和其余红色。

我需要一种算法来找到树中的最大独立集。我想从所有叶子节点开始，然后删除这些叶子节点的直接父节点，然后选择我们删除的父节点的父节点，递归地重复这个过程，直到我们到达根节点。这是在 O(n) 时间内完成的吗？任何答复表示赞赏。谢谢。

谁能给我一个算法来找到树中的最大支配集。

我们需要一种算法来生成无向图的所有独立集。

例如：

我们尝试使用“Bron-Kerbosch”算法，但不明白如何解释结果。

输入：

A = [1 2; 1 5; 2 3; 2 5; 3 4; 4 5; 4 6]

期望的输出：

B = [1 3 6; 1 4; 2 4; 2 6; 3 5 6]

如何解释结果？

谢谢！

我有一个关于将 s-clique 转换为 s-独立集的算法类的作业问题。下面是代码，最底部的功能independent_set_decision(H,s)是我需要完成的。我难住了。

给定二分图。每个顶点都有一些整数值——权重。

是否可以在多项式时间内找到该图中的最大加权独立顶点集？

如果存在这样的解决方案，这个问题的算法是什么？

假设我们有一个类似于链表（或有向无环图）的图。独立集合由不与集合中任何其他节点共享边的节点组成。如果每个节点都被加权，我们如何计算独立节点集的最大可能值？我知道我们必须使用动态编程，所以我有一点线索，但我希望有人能解释他们将如何处理它。谢谢！

让我们说我有一个男人和女人的名单。每个男人 (x) 给每个女人打分，每个女人 (y) 给每个男人打分，等级为 0-9。

例如

x1：{y1：0，y2：5，y3：9}

x2：{y1：1，y2：0，y3：9}

x3：{y1：5，y2：5，y3：8}

y1：{x1：3，x2：3，x3：5}

y2：{x1：8，x2：2，x3：2}

y3：{x1：9，x2：5，x3：9}

我正在寻找一种将所有 x 和 y 配对以最大化总收视率的算法。

在这种情况下，最佳配对将是 x2:y3 = 9+9 = 18, x1:y2 = 5+8 = 13, x3:y1 = 5+9 = 14。总评分为 45。至少我认为是肉眼可见的。

我认为它是最大独立集问题的简化版本，而不是 NP-hard 优化问题。

考虑一个包含 n 个二维点的单位正方形。我们说两个点 p 和 q 在一个正方形中是独立的，如果它们之间的欧几里德距离大于 1。一个单位正方形最多可以包含 3 个相互独立的点。我想在 O(n log n) 的给定单位正方形中找到这 3 个相互独立的点。可能吗？请帮我。

这个问题是否可以在 O(n^2) 内解决而不使用任何空间数据结构，如 Quadtree、kd-tree 等？

首先，我想提一下，这是我的功课。但是，为了解决我的问题，我可以使用任何我想要的文献。

尽管我认为这个问题从它的名字就很清楚了，但我还是会给出描述：“对于给定的无向图 G 和给定的整数 k，G 是否包含大小为 k 的完全连通（团）子图或完全不连通子图（独立集）尺寸 k。”

我知道从3-SATtoCLIQUE和 from 3-SATto 的多项式归约INDEPENDENT-SET。（http://mlnotes.com/2013/04/29/npc.html）但是，我对此有疑问，因为我无法将这两种减少结合起来。我也尝试从CLIQUEto减少，CLIQUE-OR-INDEPENDENT-SET但没有多大成功。

所以我真的很感激任何提示！

提前致谢。