图形着色问题的NP完整性

Question

替代配方

我想出了以下问题的替代配方。替代配方实际上是问题的特殊情况，并使用二分图来描述问题。但是，我认为替代配方仍然是NP-HARD。替代配方使用一组不交往的传入和传出节点，可以简化问题的定义。

给定$ n $传出和$ n $传入的节点（分别为图中的红色和蓝色节点），以及一个$ w_ {ij} $ suble size of Size $ n times n $的边缘权重之间的$ w_ {ij {ij} $顶点。问题的目的是为图中的厚边缘着色，以便在每个传入节点中，条件都保持。

给定一个$ {o_i ; | ; i = 1 dots n } $的输出顶点，一个$ {i_i ; | ; i = 1 dots n } $的输入顶点，$ n times n $ weights $ w_ {ij} ge 0 $ $ o_i $'s和$ i_j $之间的$ i，$ i，j = 1 dots n $和正常数$ beta $，找到边缘$ e_ {ii} $（上图中的厚边）的最小颜色数量，以便所有$ j = 1 dots n $，

$$ frac {w_ {jj}} {1+ sum_ {c（i）= c（j），i neq j} w_ {ij}} ge beta $ beta $$

其中$ c（i）$显示边缘$ e_ {ii} $的颜色。

---

旧配方

以下问题对我来说似乎是NP-Hard，但我无法显示。任何证明/评论以表明其硬度或轻松性。

假设$ k_n = langle v，e rangle $是带有$ n $ nodes和$ n（n-1）$ edge的完整加权定向图。令$ w_ {ij} ge 0 $显示边缘$ ij $和$ c（ij）$的权重显示边缘$ ij $的颜色。给定边缘的子集$ t subseteq e $和一个正常数$ beta $，目标是：找到最小数量的颜色，以便为每个$ e_ {ij} in t $：

$$ frac {w_ {ij}} {1+ sum_ {c（kl）= c（ij），kl neq ij} w_ {kj}}} ge beta。 $$和$$ c（ij） neq c（ik） quad for quad j neq k $$

请注意，在上面的问题中，只有$ t $中的边缘才需要颜色。这就是问题可以在$ mathcal {o}（| t |！）$中解决。

更新：

在Tsuyoshi Ito的评论之后，我更新了问题。分母从$ 1+ sum_ {c（kj）= c（ij），k neq i，e_ {kj} in t} w_ {kj} $ in t} （ij），kl neq ij} w_ {kj} $。因此，分母还包含$ t $之外的权重。这实际上就是为什么我提到定义中的完整图。

我还为 quad j neq k $添加了其他约束$ c（ij） neq c（ik） quad。这意味着，来自节点的传出边缘必须具有不同的颜色（但传入的颜色可能与不等式相同）。这使颜色数量直观下降，这是节点中最大的$ t $中的最大限制。

正如Tsuyoshi提到的那样，$ W_ {IJ} $，$ T $和$ beta $是问题的输入，边缘颜色是输出。

更新2：

问题不会强制执行边缘$ e_ {ij} $，而$ e_ {ji} $具有相同的颜色。

Answer 1

很容易证明替代配方是np-hard。还原来自顶点着色问题。给定具有$ n $顶点的图形G，我们使用$ n $输出顶点和$ n $输入顶点创建上述问题的实例。权重按以下方式设置：对于所有$ i $，令$ w_ {ii} = 1 $。对于$ i neq j $，如果顶点$ i $和顶点$ j $之间有边缘，让$ w_ {ij} = w_ {ji} = 1 $ } = 0 $。此外，令$ beta = 1 $。

这很明显，但很难描述为什么还原是正确的。令$ Mathcal {C} $显示图形的实例，$ Mathcal {r} $显示问题的简化实例。为了显示上述减排给出正确的解决方案，我们需要证明（1）$ Mathcal {r} $的每种有效着色也适用于$ Mathcal {C} $。 （2）$ mathcal {r} $给出的答案对于$ mathcal {c} $是最小的。

如果$ i $和$ j $是$ mathcal {c} $的两个相邻顶点，那么它们必须在$ Mathcal {r} $中具有不同的颜色。那是因为如果$ i $和$ j $相邻并且具有相同的颜色，则分数$ frac {w_ {jj}} {1+ sum_ {c（i）= c（j），i neq， j} w_ {ij}} $将导致$ frac {1} {1+x} $，其中$ x $具有正值。因此，条件不存在。此外，对于$ Mathcal {C} $，每种有效的（但不一定是最小）着色，都是$ Mathcal {R} $的有效着色。这得出的事实是，在$ Mathcal {C} $的有效着色中，每对相邻节点都有不同的颜色，因此该条件适用于解决方案中$ Mathcal {r} $的所有彩色边缘。由于$ Mathcal {C} $的每种着色都是$ Mathcal {r} $的有效着色，因此对$ Mathcal {r} $的最小解决方案必须是$ Mathcal {C} $的最小解决方案。否则，这不是最小的，因为$ Mathcal {C} $的解决方案提供了一种颜色较少的解决方案。

Answer 2

编辑: ：以下构造不太可行，根据下面的评论，它并没有强制执行$ c（ij）= c（ji）$。我将其放置，以防万一这是一个有用的开始。另外，$ t $不应包括重量$ 0 $的弧线。

按照Mohsen的建议，从边缘着色开始，将图$ g =（v，e）$转换为digraph $ d =（v，a）$在同一顶点套件上，其中$ forall uv in e $ we在$ a $中有$（u，v）$和$（v，u）$，在$（此时）重量$ w_ {a} = 1 $，然后$ forall xy xy notin e $ add $（x，y）$和$（y，x）$ to $ a $ with $ w_ {xy} = w_ {yx} = 0 $，set $ beta $ to $ 1 $和$ t = $。

然后，只有在同一顶点上没有两个弧形的弧度具有相同颜色的情况下，就会满足条件，而无视原始图中非边缘的弧线（因为它们具有$ 0 $）。然后可以将这种着色转换回原始图的合适着色。

从技术上讲，我已经将您的原始问题转换为决策问题（“可以用$ k $颜色色彩图表？”），但是无论如何，这都需要做到这一点，并且可以有效地互换到多项式。

因此，我认为这有效，或者我只是表现出其他东西是$ np $ -hard？ ）