$ text {k-key} $问题

Question

给定图形，我定义了一个称为的结构 K键 作为包含$ k $顶点的路径，该路径连接到一个简单的周期，其中还包含$ k $顶点。

这是 K键问题: ：给定无向图$ g $和一个数字$ k $，确定$ g $是否包含k $ k $ - 键。

我想证明k键问题是NP完整的。

我想从“无向的哈密顿周期”问题中减少输入是图形的问题，而问题是确定它是否包含哈密顿路径。我已经知道这个问题是NP完成的。减少的输入将是无向图$ g $，输出为$ g'$图和$ k $。您能帮我了解我应该对原始图做什么操纵以显示这种减少？为什么要工作？

Answer 1

您想找到一种从$ g $创建$ g'$的方法，以便$ g'$具有$ k $ -key iff $ g $具有汉密尔顿路径。

如果图$ g $具有$ k $的顶点和一条简单的长度$ k $的路径，那么我们可以得出什么结论？

我猜想的目的是，路径中的顶点必须与周期中的顶点不同（否则每个火腿周期图都包含$ k $ - 键，反之亦然）。因此，想一想，假设我们知道$ g $从某个顶点开始。我们在哪里可以在某些顶点上找到使用$ k $键使用$ g $的火腿周期的$ g'$？