车轮子图问题[重复

Question

这个问题在这里已经有一个答案：

• 从汉密尔顿周期问题减少到图轮问题[重复 1个答案

在以下两个线程中，我以错误的方式指定了这个问题（更易于以这种方式解决）。证明查找轮子仪是NP完整的

从汉密尔顿周期问题减少到图轮问题

我真诚的道歉..希望主持人能让我发布这个问题的最终版本。

实际上，问题是不同的，而且更困难：有没有办法确定$ n $ Vertices的图$ g $是否具有$ w_ {k} $的子图？是否可以证明这是NP完整问题？

Saeed Amiri提供的Follwig解决方案似乎仅在问题是确定整个图是车轮时工作时起作用。

我们将向图$ g $添加一个额外的顶点$ v $，然后制作新图$ g'$，因此$ v $已连接到$ g $的所有其他顶点，然后$ g $具有汉密尔顿周期如果并且仅当$ g'$具有$ w_ {n+1} $时，很容易检查如果$ g $具有汉密尔顿周期，则$ g'$具有$ w_ {n+1} $ wheel（只有另一方面，如果$ g'$具有$ w_ {n+1} $，则设置$ v $作为中心），则有两种可能性：

1. $ v $是$ w_ {n+1} rightarrow g $的中心。
2. 另一个顶点$ u $是$ g'$中的$ w_ {n+1} $的中心，但是两个$ deg（u）= deg（v）= n $，因此我们可以更改这两个顶点的标签（实际上它们在同构下是等效的），现在我们再次有可能。

PS：由$ w_n $，我的意思是带有$ n $顶点的轮子。

似乎汉密尔顿周期的方法是错误的，因为通过这种方法，我们被迫考虑整个顶点的周期。由于问题是要确定子集图的存在$ w_ {k} $，因此策略需要不同。

Answer 1

如果对$ k $没有限制，那么确定$ w_k $是$ g $的子图的问题包含一个问题的问题，即$ w_n $是$ g $的一个特殊情况，这意味着这意味着问题是NP-HARD。也许您对问题的硬度如何取决于$ k $感兴趣？这是完整的图片：

• 当$ k = n^c $用于常量$ c $时，问题仍然是填充技巧：您可以将$ k $顶点上的汉密尔顿周期问题减少到确定是否$ w_k $的问题通过执行Saeed的减少并添加$ nk $隔离的顶点，$ g $（具有$ n $顶点）的子图；

• 当$ k = omega（ log n）$时，一种决定$ g $包含$ w_k $作为多项式时间的子图的算法将暗示算法在亚指数时间中求解3SAT（因为从3SAT减少到Hamiltonian Cyceed的算法是只有线性爆炸，Saeed的减少也是如此）；这与 指数时间假设;

• 当$ k = o（ log n）$时，存在多项式时间（确定性和更简单的随机化）算法，该算法决定$ w_k $是否为$ g $的子图。这是美丽的结果 颜色编码 Alon，Yuster和Zwick的方法，它使您可以决定$ h $是任何$ h $ constant的$ g $的子图 树宽 和$ o（ log n）$顶点；在您的情况下，$ w_k $最多具有3个（我认为这是3个，但尚未验证）。

• 通常，上面的算法确定$ w_k $是否是时间$ c $ c^kn^{o（1）} $的子图，对于某些常数$ c $。这意味着，假设指数时间假设，问题不是$ k = n^{o（1）} $的np-hard。

您可以在不使用树宽的情况下了解Alon，Yuster和Zwick结果。他们的算法有一个简单的修改，用于查找适用于$ w_k $的长度$ k $的路径。

请注意，以上完全解决了在$ k $的函数中找到$ w_k $的硬度：在$ k的指数时间假设下，问题是多项式$ k $，np-inptermediate的问题是np-hard $ superlogarithmic但多种单位，并且在p上以$ k $为$ k $。

Answer 2

如前所述，Saeed Amiri的解决方案非常正确。问题似乎是您正在误解需要证明NP完整性的内容。

当然，您必须证明问题出在NP中，但是从其他帖子来看，我收集的这不是问题。

粘性点在于NP硬性问题的减少。如果我们可以构建一个多项式时间可计算的函数$ f $，则给定NP难题$ a $ a $ a $ $ a $ $ b $ 每个 实例$ a $ $ a $ 存在一些 实例$ b $ $ b $，因此，$ a $是当然的，并且仅当$ b $是“是的”时。

注意 每个 和 存在一些 部分。这意味着$ f $ aps $ a $ a $ to to to to to to tosing a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ b $是$ b $的。也就是说，在b $中拥有$ b'是完全可以的 没有 $ a' in $ b'= f（a'）$。

换句话说，如果我们将$ f（a）$作为$ a $ a $ f $的图像，那么$ f（a） subset b $都可以）= b $。

第三种方式，$ f $不需要陈述（甚至是注射）。

因此，出于您的问题，Saeed Amiri的减少需要 任何 汉密尔顿周期的实例并产生 一些 车轮子图问题的实例。碰巧的是，唯一选择的情况是$ k = n $的情况，但这没关系，减少足以显示NP硬度（因此，NP的成员资格，完整性）。

如果您想将问题更改为强制$ k <n $，那么Saeed的证明就足够了，我们添加了第二个新顶点，没有邻居。如果您想对$ k $放置进一步的限制，那么Sasho Nikolov的答案很棒。

理解这一点的另一种途径可能是考虑“限制”技术。这指出，如果$ a'$是$ a $的子问题，而$ a'$是np-hard，则$ a $也是np-hard。大多数降低都隐含地使用了这一点，就像我们在这里所做的那样。汉密尔顿周期是NP-HARD，我们将其映射到车轮子图问题的子问题（其中$ n = k $），所以这也是np-hard，因此轮毂子码头问题通常是NP-HARD（作为一个）它的子问题是）。