如何找到价带约束的二分图最大子图？

Question

我有一个双向图。我将引用相应不相交集合的红色节点和黑色节点。

我想知道如何找到一个连接诱导子最大化的红色节点，同时确保在所有子黑色结点有新价小于或等于二，“诱导”装置的数量如果两个节点连接在原始图中并且都存在于子图中，那么它们之间的边将自动包含在内。最后我想介绍一下非负边缘权重。

这可以归结为标准图算法吗？希望有一个已知的复杂性和简单的实施。

贪婪地生长子图显然是可能的。但这是最好的吗？

Answer 1

我敢肯定，这个问题属于NP-complete class，所以没有简单的方法来解决它。我建议你使用constraint satisfaction的方法。有很多方法可以解决您的问题，例如混合整数编程，MaxSAT甚至pseudo-boolean constraints。

对于第一次尝试，我会推荐MiniZinc求解器。例如，请考虑this在MiniZinc中定义和解决图形问题的示例。

Answer 2

不幸的是，这是NP难，所以可能没有多项式时间算法来解决它。这里是从NP难问题Independent Set中减去，其中给出了图G =（V，E）（其中n = | V |和m = | E |）和整数k，并且任务是确定是否有可能找到一组k或更多个顶点，使得该组中没有两个顶点通过边相连的：

• 对于G中每个顶点V_I，在H.
创建一个红色顶点R_I
• 对于G中每个边沿（V_I，v_j），创建H中执行以下操作：
  • 黑色顶点b_ij，
  • n + 1个红色顶点t_ijk（1 < = K < = N + 1），
  • 黑-N顶点u_ijk（1 < = K < = N），
  • n条边（t_ijk，u_ijk）（1 < = K < = N）
  • Ñ （r_i，b_ij），（r_j，b_ij）和（t_ij1，b_ij）的边缘（t_ijk，u_ij {k-1}）（2 < = k < = n + 1）
  • 。
• 对于每对顶点V_I，v_j，创建以下的：
  • 黑色顶点c_ij，
  • 两个边缘（R_I，c_ij）和（r_j，c_ij）。
• 将阈值设置为m（n + 1）+ k。

调用所有r_i R的集合，所有b_ij B的集合，所有c_ij C的集合，所有t_ij T的集合以及所有u_ij U的集合。

这里的一般想法是，我们迫使每个黑色顶点b_ij至少在对应于G中边缘（i，j）的端点的2个红色顶点r_i和r_j中选择一个。我们通过给定每个这些b_ij顶点3个输出边缘，其中一个（一个到t_ij1）是“必须拥有的” - 也就是说，任何其中t_ij1顶点是而非选定的解决方案都可以通过选择它来改进，如以及它连接到的其他n个红色顶点（通过在t_ijk中的顶点和u_ijk中的顶点之间交替的“摆动路径”），除去r_i或r_j以恢复没有黑色顶点具有3个或更多邻居的属性必要时提供解决方案，然后根据需要通过从C中选择顶点来最终恢复连通性。 （c_ij顶点是“连接符”：它们的存在只是为了确保我们包含的任何子集都可以被制作为单个连接组件。）

首先假设G中存在大小为k的IS。证明在H中至少存在m（n + 1）+ k个红色节点的连通感应子图X，其中每个黑色顶点在X中至多有2个邻居。

首先，在X中包含k个顶点从R对应于IS中的顶点（这样的集合必须通过假设存在）。因为这些顶点形成一个IS，所以B中没有顶点与它们中的多于1个相邻，所以对于每个顶点b_ij，我们可以安全地添加它，并且将从t_ij1开始的2n + 1个顶点的“摆动路径”好。每个这些摆动路径都包含n + 1个红色顶点，并且有m个这样的路径（G中每个边都有一个），所以现在在X中有m个（n + 1）+ k个红色顶点。最后，为了确保X是连接的，每一个顶点c_ij都加上它使得r_i和r_j都已经在X中：注意，这并不改变X中红色顶点的总数。

现在假设有一个连接的感应子图X H中至少有m（n + 1）+ k个红色节点，其中每个黑色顶点在X中至多有2个邻居。我们将证明G中有一个大小为k的IS。

H中唯一的红色顶点是R中的那些顶点和T中的顶点.R中只有n个顶点，所以如果X不包含所有m个浮动路径，它必须至多有（m-1）（n +1）+ n = m（n + 1）-1红色顶点，这与假设它至少有m（n + 1）+ k个红色顶点相矛盾。因此X必须包含所有m个假发路径。这在X中留下了k个其他红色顶点，它们必须来自R.这些顶点中没有两个顶点可以与B中的同一个顶点相邻，因为该B顶点将与3个顶点相邻：因此，这些顶点对应于G中的一个IS

由于IS的YES实例意味着您的问题的构造实例的YES实例，反之亦然，所以问题的构造实例的解决方案完全对应于IS实例的解决方案;并且由于构造显然是多项式时间的，这表明你的问题是NP难的。